树—最“有套路”的数据结构
前言
标题用“有套路”来形容一种数据结构，似乎有点不尊重的意思。不过，我倒是觉得，一种实用的学科，就是应该产生一点套路，这才能发挥体系化研究的优势，套路就是一种保证：在不投入更多创造性与努力的情况下，依旧能获得比起随意进行相关操作更好的结果。一门成熟的学科都应如是，如果研究许久，在学科所研究的许多问题的实践上还不如一些“天赋”“灵感”，那就不得不说这门学科的“伪科学”或者“水分”还是蛮大的了。
言归正传，这篇文章将会是一系列寻找算法与数据结构的文章的开篇，树由于其特性，是递归、分治等等重要算法思想的典型载体，同时套路性较强又具有一定规律和难度，上手后，也可以获得总结其他算法“套路”的必要经验。作为一个训练的开头，还是很合适了。
树的定义与理解
先简要谈谈树的抽象定义：树本质上是一种无向图（图：由顶点与路径构成的数据结构），其中，任意两个顶点之间有且只有一条路径。简而言之，树是一种具有特殊性质的图。
树的结构非常直观，而且树的大多数结构具有一个重要性质：递归。主要来说，就是树具有某一性质时，往往其子树也具有同样的性质。比如说，一个树如果是二叉搜索树，其子树也必须是二叉搜索树。
根据这样的性质，遇到树的问题，很自然会考虑如何合理使用递归算法，其实质就是：分解为子问题，最后解决基本情况，把复杂的递归过程交给计算机来处理。所以，树类型代码的特点就是简洁（不过换句话说，由于太简洁，很多思维过程又交给了计算机，有时候写对了没有都不知道:) ）
所以，面试官往往是在用树来考察你对递归算法的理解。
一般来说，树具有以下可能的形状: 普通二叉树、平衡二叉树（即叶子节点的深度相差不超过1）、完全二叉树(除了最后一层外，每层节点全部填满，最后一层若不满，必须是右边的节点缺少；每层都填满的，被称为完美二叉树)、四叉树(quadtree,即每个节点最多有四个孩子)、N叉树(每个节点最多有N个孩子)。
树的遍历
先谈谈为什么要遍历。其实对于一个数据结构的基础算法（不讨论那些奇技淫巧），重要的不过增查改删(CRUD)。对于树这样一个结构，在没有先验知识的情况下，为了使得代码量可控，考虑到树的结构是固定的（或者说每个节点/子树都具有一样的结构），我们就得依照其连接关系借助递归方法，以一种特定的顺序进行访问。当全部的节点都被访问时，这样的操作就是一个遍历。
前序遍历(pre-order traversal):
访问顺序：根-左子树-右子树
简单实现代码：
1public void preorderTraverse(TreeNode root){2 visit(root); // 此步执行遍历的功能，比如说打印、比较、存储等等3 preorderTraverse(root.left);4 preorderTraverse(root.right);5}应用场景：在树中进行搜索、创建一棵新的树（没有根，左右子树创建后不便于连接）。
中序遍历(inorder Traverse)与后序遍历(postorder Traverse):
基本同前序遍历，只是顺序上，中序是左-根-右，后序是左-右-根。
中序遍历可写作这样的递归形式：
1public void inorderTraverse(TreeNode root){2 inorderTraverse(root.left);3 visit(root); // 此步执行遍历的功能，比如说打印、比较、存储等等4 inorderTraverse(root.right);5}可以看到，此时也并不复杂，只是单纯地换序而已，将在根处的操作移动到了中间，规律明显，代码也易于阅读。
对于中序遍历，其应用场景最常见的是二叉搜索树，按这样的顺序遍历出来，输出的结果是按大小顺序的（比如说递增）。
关于后序遍历，如果在对某个节点进行分析时，需要其左右子树的信息（大小、存在与否等等），那么可以考虑后序遍历，仿佛就是在修剪一棵树的叶子，可以从外向内不断深入修剪。
由于三种遍历说的前中后都是针对根节点，国内也有教材把上述遍历方式称为，先根遍历、中根遍历、后根遍历，前中后决定的只是根的位置，左子树都在右子树之前，这样记忆可能简单些（虽然最好的记忆方法永远是实现几个代码）。
不过，递归写法虽然容易，非递归写法也需要掌握。
这里提供一种前序遍历的非递归写法的分析思路：
主要考虑用栈来模拟上面的递归(递归本质上也是操作系统/OS在帮你压栈，所以递归深度过深时报错也是所谓“stack overflow”，即栈溢出)：
以下出自leetcode144题，即二叉树前序遍历：
1public List<Integer> preorderTraversal(TreeNode root){ 2 List<Integer> res = new ArrayList<>(); // 用于保存遍历结果 3 Stack<TreeNode> stack = new Stack<>(); 4 TreeNode curr = root; // 用于指示当前节点 5 while(curr != null || !stack.isEmpty()){ 6 if(curr != null){ 7 res.add(curr.val); 8 stack.push(curr); 9 curr = curr.left; // 考虑左子树10 } else{11 // 节点为空，弹栈，回溯到上一层12 curr = stack.pop();13 // 此时考虑右子树14 curr = curr.right;15 }16 }17 return res;18}类似地，中序遍历可以写作以下非递归形式，除了稍微改变顺序以外，几乎跟前序遍历一样：
1public List<Integer> inorderTraversal(TreeNode root) { 2 List<Integer> res = new ArrayList(); 3 Stack<TreeNode> stack = new Stack(); 4 TreeNode curr = root; // 指示当前位置 5 6 while(curr != null || !stack.isEmpty()){ 7 if(curr != null){ 8 stack.push(curr); 9 curr = curr.left; //先入栈，并指向左节点10 } else{11 //当前节点为空时，出栈，并进行操作，随后指向右节点12 curr = stack.pop();13 res.add(curr.val);14 curr = curr.right;15 }16 }1718 return res;19 }不同于上面两个，后序遍历的非递归略微难写一点，主要是因为需要考虑根节点的问题，在整个遍历过程中，根节点会被访问两次，需要判断是否右子树已经被访问过了，才能确认根节点是否需要被保存。最简单粗暴的想法就是用hashset保存已经访问过的节点：
1class Solution { 2 public List<Integer> postorderTraversal(TreeNode root) { 3 List<Integer> res = new ArrayList(); 4 Stack<TreeNode> stack = new Stack(); 5 Set<TreeNode> set = new HashSet<>(); 6 TreeNode curr = root; 7 8 while(curr != null || !stack.isEmpty()){ 9 // 首先不断向左子树运动10 while(curr != null && !set.contains(curr)){11 stack.push(curr);12 curr = curr.left;13 }14 // 此时不能直接保存根节点再去右子树，所以只能利用peek来寻找右子树15 curr = stack.peek();16 // 若右子树为空，或者已经访问过一次这个节点，可以弹出17 if(curr.right == null || set.contains(curr)){18 res.add(curr.val);19 set.add(curr);20 stack.pop();21 // 若栈此时已经弹空，可以返回结果22 if(stack.isEmpty()){23 return res;24 }25 curr = stack.peek();26 curr = curr.right;27 } else{28 // 若不然，先向右移动，保存该点到hashset中确认已经访问过一次29 set.add(curr);30 curr = curr.right;31 }32 }33 return res;34 }35}上述解法是利用hashset来保存根节点是否已经被越过一次，但是重要的其实只是确认根节点的右子树是否被访问过，所以只需要知道上一个节点是不是其右子树就行，因此保留一个上一个节点的变量即可：
1class Solution { 2 public List<Integer> postorderTraversal(TreeNode root) { 3 List<Integer> res = new ArrayList(); 4 Stack<TreeNode> stack = new Stack(); 5 TreeNode curr = root; 6 TreeNode pre = null; 7 8 while(curr != null || !stack.isEmpty()){ 9 if(curr != null){10 stack.push(curr);11 curr = curr.left;12 } else{13 TreeNode temp = stack.peek();14 // 考虑是否变为右子树15 if(temp.right != null && temp.right != pre){16 curr = temp.right;17 } else{18 res.add(temp.val);19 pre = temp;20 stack.pop();21 }22 }23 }24 return res;25 }26}官方题解的方法则更为巧妙一点，即考虑将相关的内容逆序保存，这样巧妙地规避了根节点不便处理的问题：实现一个右、左、中的保存顺序，实现时还是按中、右、左来进行，保存数字时逆序。
利用了LinkedList特有的addFirst方法，将新出现的数值插入到链表的开头，同事时，由于stack的顺序是先进后出，所以看似是中、左、右，出栈后又是中、右、左，由于保存的顺序是每次加入到链表开头，所以实际上进行了一个逆序，完成了一个左、右、中的过程：
1class Solution { 2 public List<Integer> postorderTraversal(TreeNode root) { 3 LinkedList<TreeNode> stack = new LinkedList<>(); 4 LinkedList<Integer> output = new LinkedList<>(); 5 if (root == null) { 6 return output; 7 } 8 9 stack.add(root);10 while (!stack.isEmpty()) {11 TreeNode node = stack.pollLast();12 output.addFirst(node.val);13 if (node.left != null) {14 stack.add(node.left);15 }16 if (node.right != null) {17 stack.add(node.right);18 }19 }20 return output;21 }22}除了使用那么复杂的办法，也有一种“投机取巧”的办法，就是先做中-右-左的遍历，然后把遍历结果逆序，也就得到了后序遍历结果了。修改我们上面出现过的前序遍历代码也不难得到类似结果：
1public List<Integer> postorderTraversal(TreeNode root){ 2 List<Integer> res = new ArrayList<>(); // 用于保存遍历结果 3 Stack<TreeNode> stack = new Stack<>(); 4 TreeNode curr = root; // 用于指示当前节点 5 while(curr != null || !stack.isEmpty()){ 6 if(curr != null){ 7 res.add(curr.val); 8 stack.push(curr); 9 curr = curr.right; // 考虑右子树10 } else{11 // 节点为空，弹栈，回溯到上一层12 curr = stack.pop();13 // 此时考虑右子树14 curr = curr.left;15 }16 }17 Collections.reverse(res); // 直接使用内置的逆序，不必在插入时一一进行操作18 return res;19}当然，如果要多做一点优化，可以模仿前一个结果，在添加到res时使用addFirst方法。对于java实现，这里有一个小细节，在声明时，必须使用LinkedList，因为List不提供addFirst方法接口。
经典例题回顾：
讲了基本的定义与三个遍历的递归与非递归写法，其实树的基础知识已经足够了，基本上遇到题目稍做变化就行了，不信？直接上一些看似复杂的题目看看吧。
leetcode250题（后序遍历）：统计有多少个子树拥有相同的数字。
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
给定一个二叉树，统计其uni-value子树的个数。
一个uni-value子树指的是这个子树的全部节点的值相同。
一段有问题的代码(对于测试样例[5,1,5,5,5,null,5]，正确答案4，输出结果2)：
1class Solution { 2 int count = 0; 3 public int countUnivalSubtrees(TreeNode root) { 4 postorder(root); // 从根节点开始遍历 5 return count; 6 } 7 8 public boolean postorder(TreeNode root){ 9 if(root == null) return true;10 if(postorder(root.left) && postorder(root.right)){11 if(root.left != null && root.left.val != root.val) return false;12 if(root.right != null && root.right.val != root.val) return false;13 count++;14 return true;15 }16 return false;17 }18}可通过的代码：
1class Solution { 2 int count = 0; 3 public int countUnivalSubtrees(TreeNode root) { 4 postorder(root); 5 return count; 6 } 7 8 public boolean postorder(TreeNode root){ 9 if(root == null) return true;10 if(postorder(root.left) & postorder(root.right)){11 if(root.left != null && root.left.val != root.val) return false;12 if(root.right != null && root.right.val != root.val) return false;13 count++;14 return true;15 }16 return false;17 }18}在完成这题的过程中，我犯了一些错误，主要在于没有深刻理解递归：
- 在使用判断条件postorder(root.left)以及postorder(root.right)时，实际上已经发生了递归；（所以假定这题是前序遍历或中序遍历会很难完成代码的构造）
- 在java中，使用&&会出现短路，即前半部分已经false了之后，会自动不执行后半部分，因此为了逻辑的正确，此处只能使用&。
leetcode230题：
求在二叉搜索树（BST）中第k小的值，本题主要考虑使用中序遍历，因为二叉搜索树中序遍历是一个递增的数列：
唯一需要注意的就是左子树遍历完成后，有可能还没有达到k，那么可以设定Integer.MAX_VALUE作为没有找到的标志，防止未找到。
这个算法遍历的时间空间复杂度是O(k)，最坏的情况下有可能达到O(N)。（在leetcode平台上打败了100%的java程序）
1class Solution { 2 int count = 0; 3 public int kthSmallest(TreeNode root, int k) { 4 if(root.left != null){ 5 int res = kthSmallest(root.left, k); 6 if(res != Integer.MAX_VALUE) return res; // 若未能寻找到，应继续向右搜索 7 } 8 count++; 9 if(count == k) return root.val;10 if(root.right != null) return kthSmallest(root.right, k); // 题目中保证了能搜索到，所以此处不必再加判断1112 return Integer.MAX_VALUE; // 若在左侧节点未寻找到，返回这个标志13 }14}相比之下，官方题解则先将全部的节点遍历到一个数组中，然后再寻找第k个，问题就在于将时间复杂度因而扩大到了O(N)。(使用这个方法，时间上只能打败49.01%的程序)
1class Solution { 2 public ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> arr) { 3 if (root == null) return arr; 4 inorder(root.left, arr); 5 arr.add(root.val); 6 inorder(root.right, arr); 7 return arr; 8 } 910 public int kthSmallest(TreeNode root, int k) {11 ArrayList<Integer> nums = inorder(root, new ArrayList<Integer>());12 return nums.get(k - 1);13 }14}leetcode366题：
Given a binary tree, collect a tree‘s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.
给定一个二叉树，返回一个树的节点的集合的集合，每次都收集并移除当前的所有的叶子节点，直到整个树为空。
这是一个很有趣的题目，因为如果从上向下遍历，是不难的，直接使用BFS（宽度优先搜索），这样的方式又叫“层次遍历”（level-order traversal）；然而，从下往上则无这个顺序，左右子树的深度非常有可能不同，而叶子节点只需要左右子树不存在即可。
本题可采用了刚才所谓的“剥洋葱”的办法，因此可以先考虑后序遍历（本题算是一种变体）：
1class Solution { 2 public List<List<Integer>> findLeaves(TreeNode root) { 3 List<List<Integer>> res = new ArrayList(); 4 while(root != null){ 5 List<Integer> curr = new ArrayList(); 6 root = upward(root, curr); 7 res.add(curr); 8 } 9 return res;10 }1112 public TreeNode upward(TreeNode root, List<Integer> curr){13 // 函数的功能是将所有叶子节点保存到curr中，然后把叶子节点置为null14 if(root == null) return null;15 if(root.left == null & root.right == null){16 // 如果是叶子节点，加入curr，然后返回null17 curr.add(root.val);18 return null;19 }20 // 如果不是叶子节点，递归调用其左右子树，保存新的情况21 root.left = upward(root.left, curr);22 root.right = upward(root.right, curr);23 return root;24 }25}这一题算是使用了一种变体方法，不过本质上还是一种后序遍历。
当然，这题也可以不修改树，直接考虑DFS(深度优先搜索)再回溯，但是就需要引入一个判断深度的指标来进行控制了：
1class Solution { 2 public List<List<Integer>> findLeaves(TreeNode root) { 3 List<List<Integer>> res = new ArrayList(); 4 postorder(root,res); 5 return res; 6 } 7 8 public int postorder(TreeNode root, List<List<Integer>> res){ 9 if(root == null) return -1; // 空节点置为-1，因为叶子节点是010 // 递归调用获取当前深度（准确的说，其实是从叶子节点开始的高度）11 int depth = 1 + Math.max(postorder(root.left,res),postorder(root.right,res));12 // 根据java语法，如果还没有list对象，需要先创建13 if(depth >= res.size()) res.add(new ArrayList());14 // 将节点加入对应深度，由于递归必然从最深处开始，顺序不会有问题15 res.get(depth).add(root.val);16 return depth;17 }18}leetcode285：
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
The successor of a node
pis the node with the smallest key greater thanp.val.给定一个二叉搜索树，并给定一个节点，寻找这个节点的中序遍历的后续节点。
寻找二叉搜索树的中序遍历后继，可以从递归和迭代两种方法完成，由于已经暗示明白了，直接使用中序遍历即可解决这一问题：
递归法依旧有容易阅读的优点，不过构造时不必想太复杂，直接使用前序节点来保存前一个数据即可。(此时已经达到了不错的结果，时间达到了92%)
1class Solution { 2 TreeNode pre = null; 3 TreeNode ans = null; 4 public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { 5 if(root == null || p == null) return null; 6 inorderSuccessor(root.left, p); 7 if(pre == p){ // 条件也可改为 pre != null && pre.val == p.val 8 // 如果其前继节点已经满足条件，则保存结果 9 ans = root;10 }11 pre = root;12 inorderSuccessor(root.right,p);13 return ans;14 }15}非递归方法：这一方法直接改自中序遍历，不过实际上没有充分利用BST暗含的规律，所以速度不是最快的，仅仅达到了28.88%。
1class Solution { 2 public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { 3 if(curr == null || p == null) return null; 4 Stack<TreeNode> stack = new Stack(); 5 TreeNode curr = root; 6 boolean foundP = false; 7 while(root != null || !stack.isEmpty()){ 8 if(curr != null){ 9 stack.push(curr);10 curr = curr.left;11 } else{12 curr = stack.pop();13 if(foundP == true){14 return curr;15 }16 if(curr.val == p.val){17 foundP = true;18 }19 curr = curr.right;20 }21 }22 return null;23 }24}不得不说，使用遍历来解决树问题，实在是颇有“一招鲜吃遍天”的感觉，甚至略加改进就能解决hard级的leetcode99题。
leetcode99题:
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
一个二叉搜索树的两个元素被交换了。
复原这个树，使得它符合BST结构，但不改变树的整体结构。
这题就是恢复二叉搜索树的问题。看到BST，几乎是一个中序遍历的问题。本题需要注意的地方就是，被交换的节点存在两种可能性，一种是相邻节点的顺序反了，那么，直接交换值即可，另外一种是相隔的节点顺序错了，因此还需要保存第二次发生前序节点大于当前节点的位置。（以下主要由中序遍历模板改出）
非递归：
1class Solution { 2 public void recoverTree(TreeNode root) { 3 Stack<TreeNode> stack = new Stack(); 4 TreeNode prev = null, curr = root; 5 TreeNode first = null, second = null; // 用于保存改变的第一个和第二个位置 6 7 while(curr != null || !stack.isEmpty()){ 8 if(curr != null){ 9 stack.push(curr);10 curr = curr.left;11 } else{12 curr = stack.pop();13 // 如果发生了前序节点大于当前节点，分两种情况14 if(prev != null && prev.val > curr.val){15 // 如果是第一次遇到，保存first为前序，second为当前16 if(first == null){17 first = prev;18 second = curr;19 } else{20 // 如果第二次遇到，只重新保存当前值到second中21 second = curr;22 }23 }24 prev = curr;25 curr = curr.right;26 }27 }28 int temp = first.val;29 first.val = second.val;30 second.val = temp;31 }32}递归：
1class Solution { 2 TreeNode first = null; 3 TreeNode second = null; 4 TreeNode prev = null; 5 public void recoverTree(TreeNode root) { 6 inorder(root); 7 int temp = first.val; 8 first.val = second.val; 9 second.val = temp;10 }1112 public void inorder(TreeNode root){13 if(root == null) return;14 inorder(root.left);15 // 对前序节点进行判断16 if(prev != null && prev.val > root.val){17 // 第一次遇到则全部保存18 if(first == null){19 first = prev;20 second = root;21 } else{22 // 第二次遇到只保存second23 second = root;24 }25 }26 // 更新prev节点27 prev = root;28 inorder(root.right);29 }30}简要总结
树的题目大多来自三种遍历的变体，一般而言，稍作一些修改就能得到一个能运行的结果（实在不行先全部遍历一遍保存到数组里来解决）；不过，为了得到最优解，往往还需要根据题目已有的一些条件或者性质，对递归进行一些优化（如结束递归的条件，递归的方式等等）；有时递归不便于进行一些细节操作时，可以考虑用非递归写法（当然，由于递归写法解题有时太轻松，出于面试难度问题，面试官也往往会要求非递归，也算是为学习非递归多一个理由吧！）。