文/TWOTO

二叉树是面试中常见的题目类型，这里，针对leetcode前200道题中的二叉树相关问题进行总结与思考，力求烂熟于心，能根据题目名回忆起题目的具体描述，进而用简洁的语言描述出算法的核心。具体的题目答案可打开leetcode查看历史提交记录。

二叉树的遍历（binary-tree-traversal）

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

为什么研究二叉树的遍历？
因为计算机只会处理线性序列，而我们研究遍历，就是把树中的结点变成某种意义的线性序列，这给程序的实现带来了好处。

1 三种基本遍历方式

首先是二叉树的遍历方式，最简单基础的也就是前序(preorder)、中序(inorder)、后序(postorder)三种遍历方式，对应题目 144.二叉树的前序遍历 、94. 二叉树的中序遍历 、145. 二叉树的后序遍历。

前中后，指的是根节点相对于左右结点的访问顺序

先序：考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)

中序：考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)

后序：考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)

image.png

这种类型的题一般都是有两种解题思路：递归和迭代。

1.1 递归法模板

我们并不需要太过于在意具体的递归过程，而是要想清楚让计算机干什么。计算机都可能溢出，用人脑去遍历就不现实了。

思路： 判断什么时候把结点的val加入res数组中，res.add(root.val)放的位置决定了遍历顺序。

  1. 边界条件
  3. 定义 dfs 函数：
  4.     如果root为空：返回
  5.     递归左子树
  6.     递归右子树
  7.     // root 的值加入到结果
  9. 执行递归函数，返回结果
  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> res=new ArrayList<>();
  4.         helper(root,res);
  5.         return res;    
  6.     }
  7.     // 递归主程序
  8.     private void  helper(TreeNode root,List<Integer> res) {
  9.         // 判断root是否为空，是一个重要的递归终止的条件。
  10.         if(root==null) return;
  11.         // res.add(root.val);
  12.         helper(root.left,res);
  13.         helper(root.right,res);
  14.     }
  15. }

一样的代码，稍微调用一下位置就可以，如此固定的套路，使得只掌握递归解法并不足以令面试官信服=`=所以必须掌握迭代法加深对二叉树的理解！！

1.2 迭代法模板

本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈。

思路：用while循环先将根节点和所有左孩子加入栈和结果数组中，直至cur为空。然后，每弹出一个栈顶元素 tmp，就到达它的右孩子，再将这个节点当作 cur 重新按上面的步骤来一遍，直至栈为空。这里又需要一个 while 循环。

使用这个迭代模板处理前序和中序遍历，只要更改 res.add(cur.val) 的位置即可。

  1. 边界条件
  3. 初始化stack,res,cur
  4. while stack或cur 非空：
  5.     while cur非空：
  6.         cur的值入栈stack
  7.         // cur的值加入res 前序
  8.         cur 向左下或右下遍历
  9.     弹出节点tmp
  10.     cur回到tmp的左或右子树
  12. 返回结果
  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> res=new ArrayList<>();
  4.         Deque<TreeNode> stack = new LinkedList<>();
  5.         TreeNode cur=root;
  6.         while(cur!=null||!stack.isEmpty()){
  7.             while(cur!=null){
  8.                 stack.push(cur);
  9.                 //res.add(cur.val);前序
  10.                 cur=cur.left;
  11.             }
  12.             tmp=stack.pop();
  13.             //res.add(tmp.val);中序
  14.             cur=tmp.right;
  15.         }
  16.         return res;  
  17.     }
  18. }

但是后序并不能使用，取巧的方法是使用模板(根右左)，对其取反Collections.reverse(res)就是后序遍历的结果(左右根)

利用了结果的特点反向输出，不免显得技术含量不足，因此掌握后序遍历标准的栈操作解法是必要的！

  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> res=new ArrayList<>();
  4.         Deque<TreeNode> stack=new LinkedList<>();
  5.         TreeNode cur=root;
  6.         TreeNode p=null;
  7.         while(cur!=null || !stack.isEmpty()){
  8.             while(cur!=null){
  9.                 stack.push(cur);
  10.                 cur=cur.left;
  11.             }
  12.             //peek不删除栈顶，pop删除
  13.             cur=stack.peek();
  14.             // 一种情况是cur为最下面的子节点，需要加入到res，另一种是当前为遍历过右子树的根节点也需要加入到res
  15.             if(cur.right==null||cur.right==p){
  16.                 res.add(cur.val);
  17.                 stack.pop();
  18.                 p=cur;
  19.                 cur=null;
  20.             }else{
  21.                 cur=cur.right;
  22.             }
  23.         }
  24.         return res;
  25.     }  
  26. }

2 层序遍历及其变题

除了基本的三种遍历使用DFS，使用BFS广度优先搜索的层序遍历也很重要102. 二叉树的层序遍历

下面是两种解决此类问题的方法，一般使用左边的BFS

leetcode 总结——遍历二叉树 - 图2

2.1 BFS层序遍历

BFS遍历的标准写法如下，使用的是队列数据结构：

  1. void bfs(TreeNode root) {
  2.     Queue<TreeNode> queue = new ArrayDeque<>();
  3.     queue.add(root);
  4.     while (!queue.isEmpty()) {
  5.         TreeNode node = queue.poll(); // Queue 中 remove() 和 poll()都是用来从队列头部删除一个元素。
  6.         if (node.left != null) {
  7.             queue.add(node.left);
  8.         }
  9.         if (node.right != null) {
  10.             queue.add(node.right);
  11.         }
  12.     }
  13. }

我们可以直接用 BFS 得出层序遍历结果。然而，层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层，见下图的对比。

leetcode 总结——遍历二叉树 - 图3
因此，我们需要在每一层前微修改一下代码，在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的节点数量），然后一口气处理完这一层的 n个

结点。

  1. public List<List<Integer>> levelOrder(TreeNode root) {
  2.     List<List<Integer>> res = new ArrayList<>();
  4.     Queue<TreeNode> queue = new ArrayDeque<>();
  5.     if (root != null) {
  6.         queue.add(root);
  7.     }
  8.     while (!queue.isEmpty()) {
  9.         int n = queue.size();
  10.         List<Integer> level = new ArrayList<>();
  11.         for (int i = 0; i < n; i++) { 
  12.             TreeNode node = queue.poll();
  13.             level.add(node.val);
  14.             if (node.left != null) {
  15.                 queue.add(node.left);
  16.             }
  17.             if (node.right != null) {
  18.                 queue.add(node.right);
  19.             }
  20.         }
  21.         res.add(level);
  22.     }
  24.     return res;
  25. }

这样，我们就可以用BFS来解决层序遍历问题了，重点是记录了每一层节点的数量，动图如下

leetcode 总结——遍历二叉树 - 图4

2.2 (选看)DFS层序遍历

DFS 遍历标准写法如下，使用的是递归

  1. void dfs(TreeNode root) {
  2.     if (root == null) {
  3.         return;
  4.     }
  5.     dfs(root.left);
  6.     dfs(root.right);
  7. }

看起来比BFS的代码简洁很多，但观看下图就可以发现两者的遍历顺序是不同的，BFS其实更贴近我们想要的层序遍历逻辑。
leetcode 总结——遍历二叉树 - 图5

那DFS究竟可不可以解决层序遍历问题呢？当然是可以的！
把这个二叉树的样子调整一下，摆成一个田字形的样子。
leetcode 总结——遍历二叉树 - 图6leetcode 总结——遍历二叉树 - 图7

田字形的每一层就对应一个 list，每次递归的时候都需要带一个 index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的 list 不存在，就加入一个空 list 进去。代码实现如下。

  1. import java.util.*;    
  2. class Solution {
  3.     public List<List<Integer>> levelOrder(TreeNode root) {
  4.         if(root==null) {
  5.             return new ArrayList<List<Integer>>();
  6.         }
  7.         //用来存放最终结果
  8.         List<List<Integer>> res = new ArrayList<List<Integer>>();
  9.         dfs(1,root,res);
  10.         return res;
  11.     }
  13.     void dfs(int index,TreeNode root, List<List<Integer>> res) {
  14.         //假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
  15.         if(res.size()<index) {
  16.             res.add(new ArrayList<Integer>());
  17.         }
  18.         //将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
  19.         //res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
  20.         res.get(index-1).add(root.val);
  21.         //递归的处理左子树，右子树，同时将层数index+1
  22.         if(root.left!=null) {
  23.             dfs(index+1, root.left, res);
  24.         }
  25.         if(root.right!=null) {
  26.             dfs(index+1, root.right, res);
  27.         }
  28.     }
  29. }

感觉有点像二叉树的前序遍历，根左右

2.3 (变题) 二叉树的锯齿形层次遍历

该题是leetcode103题，medium难度，一句话题干描述：层序遍历，不过是之字形的。
总体思路：用个变量flag来判断是从左往右还是从右往左打印
解决方案1(容易理解)： 在层序遍历代码的基础上，更改节点数值进入list的顺序

  1. if (leftToRight) {
  2.     level.add(node.val);
  3. } else {
  4.     level.add(0, node.val);
  5. }

解决方案2(画图理解)： 使用deuqe双端队列：可以在两边同时添加和删除的队列

  1. # Deque<TreeNode> deque=new LinkedList<>();
  2. if (leftToRight) {
  3.     //从左边往右边打印
  4.     //移除队列头部的元素，如果子节点不为空加入到队列的尾部
  5.     cur = deque.removeFirst();
  6.     if (cur.right != null)
  7.         deque.addLast(cur.right);
  8.     if (cur.left != null)
  9.         deque.addLast(cur.left);
  10. } else {
  11.     //从右边往左边打印
  12.     //移除队列尾部的元素，如果子节点不为空加入到队列的头部
  13.     cur = deque.removeLast();
  14.     if (cur.left != null)
  15.         deque.addFirst(cur.left);
  16.     if (cur.right != null)
  17.         deque.addFirst(cur.right);
  18. }
  19. level.add(cur.val);

deque中把每一行的节点值反序列表示，然后每次打印判断从左往右读deque还是从右往左。读的时候相应的也要改变左右孩子入队列的顺序来保持 deque中每一行的节点值反序表示。

2.4 (变题) 二叉树的右视图

该题是leetcode199题，medium难度，一句话题干描述：从上到下返回每一层最后一个元素
总体思路：利用 BFS 进行层次遍历，记录下每层的最后一个元素。
解决方案1(BFS)： 在层序遍历代码基础上，判断当前节点是不是这层的最后一个节点，是的话才添加进结果数组。

  1. if(i==n-1) res.add(cur.val);

解决方案2(DFS)：我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问，就可以保证每层都是最先访问最右边的节点的。（与先序遍历 「根结点 -> 左子树 -> 右子树」 正好相反，先序遍历每层最先访问的是最左边的节点）

  1. class Solution {
  2.     List<Integer> res= new ArrayList<>();
  3.     public List<Integer> rightSideView(TreeNode root) {
  4.         dfs(root,0);
  5.         return res;
  6.     }
  7.     private void dfs(TreeNode root,int depth) {
  8.         if(root==null) return ;
  9.         if(depth==res.size()){
  10.             res.add(root.val);
  11.         }
  12.         depth++;
  13.         dfs(root.right,depth);
  14.         dfs(root.left,depth);
  15.     }
  16. }

2.5 (变题) 填充每个节点的下一个右侧节点指针

leetcode 总结——遍历二叉树 - 图8
该题是leetcode116题，medium难度，一句话题干描述：使得每个节点的next指针指向它右侧的节点(完全二叉树)
总体思路：利用 BFS 进行层次遍历队列，队列中保存了第 i 层节点的信息，我们利用这个特点，将队列中的元素都串联一遍就可以了。
解决方案1(基础版)：使用队列，直接把层序遍历的代码改一改， 把每一层的节点连接起来,这种方法同样适用于不是完全二叉树的情况。

  1.  while(!queue.isEmpty()){
  2.      int size=queue.size();
  3.      //前一个节点
  4.      Node pre = null;
  5.      for (int i = 0; i < size; i++) {
  6.          //出队
  7.          Node node = queue.poll();
  8.          //如果pre为空就表示node节点是这一行的第一个，
  9.          //没有前一个节点指向他，否则就让前一个节点指向他
  10.          if (pre != null) {
  11.              pre.next = node;
  12.          }
  13.          //然后再让当前节点成为前一个节点
  14.          pre = node;
  15.          //层序遍历的代码：左右子节点如果不为空就入队
  16.          if (node.left != null)
  17.              queue.add(node.left);
  18.          if (node.right != null)
  19.              queue.add(node.right);
  20.      }
  21.  }

上面运行效率并不是很高，这是因为我们把节点不停的入队然后再不停的出队，其实可以不需要队列，每一行都可以看成一个链表比如第一行就是只有一个节点的链表，第二行是只有两个节点的链表
解决方案2(优化版)：观察这样的串联树可以发现，有两种了连接方式

  1. 两个串联的节点都有一个共同的父节点，通过父节点就可以将这两个子节点串联起来
  2. 这两个串联的节点的父节点不同，对于这种情况，如果我们能将这一层的上一层串联好。那么可以通过父节点的 next 找到邻居，完成串联。即 root.right.next => root.next.left，这里我们需要保证 root.next 不为空就可以了。

leetcode 总结——遍历二叉树 - 图9

  1. Node pre=root;
  2. //当前节点的left为空则退出循环
  3. while(pre.left!=null){
  4.     Node tmp=pre;
  5.     // 这层连接完成，则退出
  6.     while(tmp!=null){
  7.         //将tmp的左右节点都串联起来
  8.         //注:外层循环已经判断了当前节点的left不为空
  9.         tmp.left.next = tmp.right;
  10.         //下一个不为空说明上一层已经帮我们完成串联了
  11.         if(tmp.next!=null) {
  12.             tmp.right.next = tmp.next.left;
  13.         }
  14.         //继续右边遍历
  15.         tmp = tmp.next;
  16.     }
  17.     //从下一层的最左边开始遍历
  18.     pre = pre.left;
  19. }

解决方案3(递归骚操作)：递归从上往下，先处理当前节点，再处理它的左、右子树中的节点——前序遍历。
递归终止条件：当遍历到叶子节点，没有孩子节点。

leetcode 总结——遍历二叉树 - 图10

  1. public Node connect(Node root) {
  2.     dfs(root);
  3.     return root;
  4. }
  5. void dfs(Node root){
  6.     if(root==null) return ;
  7.     if(root.left!=null){
  8.         root.left.next = root.right;
  9.         if (root.next!=null){
  10.             root.right.next = root.next.left;
  11.         }     
  12.     }
  13.     connect(root.left);
  14.     connect(root.right);
  15. }
  16. // 更牛逼的写法
  17. private void dfs(Node node, Node next) {
  18.     if(node != null) {
  19.         node.next = next;
  20.         dfs(node.left, node.right);
  21.         dfs(node.right, node.next != null ? node.next.left : null);
  22.     }
  23. }

总结：每个 node 左子树的 next , 就是 node 的右子树、每个 node 右子树的 next, 就是 node next 的 左子树


2.6 (变题) 填充每个节点的下一个右侧节点指针II

该题是leetcode117题，medium难度，一句话题干描述：使得每个节点的next指针指向它右侧的节点(非完全二叉树)
总体思路：和上一题一样的思路
解决方案1(基础版)：使用队列，直接把层序遍历的代码改一改， 把每一层的节点连接起来,同上一题代码，略。
解决方案2(优化版)：更改上一题的相关代码，增加哑节点(找到下一层的第一个节点)，此代码也可用于上题

leetcode 总结——遍历二叉树 - 图11

  1. Node cur=root;
  2. //当前节点的left为空则退出循环
  3. while(cur!=null){
  4.     Node dummy = new Node(0);
  5.     //pre表示访下一层节点的前一个节点
  6.     Node pre = dummy;
  7.     // 这层连接完成，则退出
  8.     while(cur!=null){
  9.         //如果当前节点的左子节点不为空，就让pre节点的next指向他，也就是把它串起来
  10.         if(cur.left!=null){
  11.             pre.next=cur.left;
  12.             pre=pre.next;
  13.         }
  14.         if(cur.right!=null){
  15.             pre.next=cur.right;
  16.             pre=pre.next;
  17.         }
  18.         //继续访问这一行的下一个节点
  19.         cur = cur.next;
  20.     }
  21.    //把下一层串联成一个链表之后，让他赋值给cur，后续继续循环，直到cur为空为止
  22.    cur = dummy.next;
  23. }

此外，除了这些题外，还有以下题
637.二叉树的层平均值
429.N叉树的前序遍历
515.在每个树行中找最大值

参考资料：leetcode题解，感谢这些大佬的配图以及易懂的语言！！