Leetcode总结—二叉树的遍历

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

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

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

为什么研究二叉树的遍历？

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

1 三种基本遍历方式

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

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

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

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

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

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

1.1 递归法模板

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

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

边界条件

定义 dfs 函数：
    如果root为空：返回
    递归左子树
    递归右子树
    // root 的值加入到结果

执行递归函数，返回结果

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        helper(root,res);
        return res;    
    }
    // 递归主程序
    private void  helper(TreeNode root,List<Integer> res) {
        // 判断root是否为空，是一个重要的递归终止的条件。
        if(root==null) return;
        // res.add(root.val);
        helper(root.left,res);
        helper(root.right,res);
    }
}

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

1.2 迭代法模板

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

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

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

边界条件
    
初始化stack,res,cur
while stack或cur 非空：
    while cur非空：
        cur的值入栈stack
        // cur的值加入res 前序
        cur 向左下或右下遍历
    弹出节点tmp
    cur回到tmp的左或右子树
        
返回结果

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                //res.add(cur.val);前序
                cur=cur.left;
            }
            tmp=stack.pop();
            //res.add(tmp.val);中序
            cur=tmp.right;
        }
        return res;  
    }
}

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

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

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        Deque<TreeNode> stack=new LinkedList<>();
        TreeNode cur=root;
        TreeNode p=null;
        while(cur!=null || !stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            //peek不删除栈顶，pop删除
            cur=stack.peek();
            // 一种情况是cur为最下面的子节点，需要加入到res，另一种是当前为遍历过右子树的根节点也需要加入到res
            if(cur.right==null||cur.right==p){
                res.add(cur.val);
                stack.pop();
                p=cur;
                cur=null;
            }else{
                cur=cur.right;
            }
        }
        return res;
    }  
}

2 层序遍历及其变题

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

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

2.1 BFS层序遍历

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

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Queue 中 remove() 和 poll()都是用来从队列头部删除一个元素。
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

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

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

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();

    Queue<TreeNode> queue = new ArrayDeque<>();
    if (root != null) {
        queue.add(root);
    }
    while (!queue.isEmpty()) {
        int n = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < n; i++) { 
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        res.add(level);
    }

    return res;
}

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

2.2 (选看)DFS层序遍历

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

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}

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

那DFS究竟可不可以解决层序遍历问题呢？当然是可以的！

把这个二叉树的样子调整一下，摆成一个田字形的样子。

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

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

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

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

该题是leetcode103题，medium难度，一句话题干描述：层序遍历，不过是之字形的。

总体思路：用个变量flag来判断是从左往右还是从右往左打印

解决方案1(容易理解)： 在层序遍历代码的基础上，更改节点数值进入list的顺序

if (leftToRight) {
    level.add(node.val);
} else {
    level.add(0, node.val);
}

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

# Deque<TreeNode> deque=new LinkedList<>();
if (leftToRight) {
    //从左边往右边打印
    //移除队列头部的元素，如果子节点不为空加入到队列的尾部
    cur = deque.removeFirst();
    if (cur.right != null)
        deque.addLast(cur.right);
    if (cur.left != null)
        deque.addLast(cur.left);
} else {
    //从右边往左边打印
    //移除队列尾部的元素，如果子节点不为空加入到队列的头部
    cur = deque.removeLast();
    if (cur.left != null)
        deque.addFirst(cur.left);
    if (cur.right != null)
        deque.addFirst(cur.right);
}
level.add(cur.val);

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

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

该题是leetcode199题，medium难度，一句话题干描述：从上到下返回每一层最后一个元素

总体思路：利用 BFS 进行层次遍历，记录下每层的最后一个元素。

解决方案1(BFS)： 在层序遍历代码基础上，判断当前节点是不是这层的最后一个节点，是的话才添加进结果数组。

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

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

class Solution {
    List<Integer> res= new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root,0);
        return res;
    }
    private void dfs(TreeNode root,int depth) {
        if(root==null) return ;
        if(depth==res.size()){
            res.add(root.val);
        }
        depth++;
        dfs(root.right,depth);
        dfs(root.left,depth);
    }
}

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

该题是leetcode116题，medium难度，一句话题干描述：使得每个节点的next指针指向它右侧的节点(完全二叉树)

总体思路：利用 BFS 进行层次遍历队列，队列中保存了第 i 层节点的信息，我们利用这个特点，将队列中的元素都串联一遍就可以了。

解决方案1(基础版)：使用队列，直接把层序遍历的代码改一改， 把每一层的节点连接起来,这种方法同样适用于不是完全二叉树的情况。

while(!queue.isEmpty()){
    int size=queue.size();
    //前一个节点
    Node pre = null;
    for (int i = 0; i < size; i++) {
        //出队
        Node node = queue.poll();
        //如果pre为空就表示node节点是这一行的第一个，
        //没有前一个节点指向他，否则就让前一个节点指向他
        if (pre != null) {
            pre.next = node;
        }
        //然后再让当前节点成为前一个节点
        pre = node;
        //层序遍历的代码：左右子节点如果不为空就入队
        if (node.left != null)
            queue.add(node.left);
        if (node.right != null)
            queue.add(node.right);
    }
}

上面运行效率并不是很高，这是因为我们把节点不停的入队然后再不停的出队，其实可以不需要队列，每一行都可以看成一个链表比如第一行就是只有一个节点的链表，第二行是只有两个节点的链表

解决方案2(优化版)：观察这样的串联树可以发现，有两种了连接方式

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

Node pre=root;
//当前节点的left为空则退出循环
while(pre.left!=null){
    Node tmp=pre;
    // 这层连接完成，则退出
    while(tmp!=null){
        //将tmp的左右节点都串联起来
        //注:外层循环已经判断了当前节点的left不为空
        tmp.left.next = tmp.right;
        //下一个不为空说明上一层已经帮我们完成串联了
        if(tmp.next!=null) {
            tmp.right.next = tmp.next.left;
        }
        //继续右边遍历
        tmp = tmp.next;
    }
    //从下一层的最左边开始遍历
    pre = pre.left;
}

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

递归终止条件：当遍历到叶子节点，没有孩子节点。

public Node connect(Node root) {
    dfs(root);
    return root;
}
void dfs(Node root){
    if(root==null) return ;
    if(root.left!=null){
        root.left.next = root.right;
        if (root.next!=null){
            root.right.next = root.next.left;
        }     
    }
    connect(root.left);
    connect(root.right);
}
// 更牛逼的写法
private void dfs(Node node, Node next) {
    if(node != null) {
        node.next = next;
        dfs(node.left, node.right);
        dfs(node.right, node.next != null ? node.next.left : null);
    }
}

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

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

该题是leetcode117题，medium难度，一句话题干描述：使得每个节点的next指针指向它右侧的节点(非完全二叉树)

总体思路：和上一题一样的思路

解决方案1(基础版)：使用队列，直接把层序遍历的代码改一改， 把每一层的节点连接起来,同上一题代码，略。

解决方案2(优化版)：更改上一题的相关代码，增加哑节点(找到下一层的第一个节点)，此代码也可用于上题

Node cur=root;
//当前节点的left为空则退出循环
while(cur!=null){
    Node dummy = new Node(0);
    //pre表示访下一层节点的前一个节点
    Node pre = dummy;
    // 这层连接完成，则退出
    while(cur!=null){
        //如果当前节点的左子节点不为空，就让pre节点的next指向他，也就是把它串起来
        if(cur.left!=null){
            pre.next=cur.left;
            pre=pre.next;
        }
        if(cur.right!=null){
            pre.next=cur.right;
            pre=pre.next;
        }
        //继续访问这一行的下一个节点
        cur = cur.next;
    }
   //把下一层串联成一个链表之后，让他赋值给cur，后续继续循环，直到cur为空为止
   cur = dummy.next;
}

此外，除了这些题外，还有以下题

637.二叉树的层平均值

429.N叉树的前序遍历

515.在每个树行中找最大值

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