四种遍历

先序、中序、后序遍历，非常简单！接下来我会用一种通用的方式完成这三种遍历哟！

保证你看完能迅速手写三种遍历的非递归！

先序遍历

递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        result.add(root.val); // 访问根节点
        preorderHelper(root.left, result); // 递归遍历左子树
        preorderHelper(root.right, result); //递归遍历右子树
    }
}

非递归

/**
 * 再写一个非递归的
 * 统一先序中序后序的写法
 * 从此压栈时再无左子树压栈，全部都是根节点和其右子树！
 * @param root
 */
private List<Integer> preorderTraversalByIteration(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    //得用一个栈来进行处理
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()){
        while (cur != null){
          	//先把根节点加入到list，然后把所有的根节点加入
          	//左节点其实也就是子树的根节点
            res.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
      	//然后拿到根节点的右子树，进行遍历
        cur = stack.pop();
        cur = cur.right;
    }
    return res;
}

Tip: 我这里再拓展一种非递归的想法吧…但是我觉得这种想法不是很好，没有通用的非递归思想简单！强烈建议使用上面的非递归思想！！！

至于为何非要提这种思想捏，原因就是 栈 如果换成 队列，左右节点顺序调一下，就是层序遍历了！

思想：

上面的非递归的做法是把一棵树看做只有根节点和右节点，先全部把根节点读完了，再去读其右节点，这样也就做到了 根 - 左 - 右
下面要讲的非递归的做法是先读根节点，然后将其加入栈，然后只要栈非空，就弹栈，将其加入需要返回的列表中，然后先将其右子树节点加入到栈中，然后将左子树节点加入到栈中，注意，这里是先右子树，后左子树，因为栈是后进先出！下一步就是左子树出栈，将其加入列表中。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) return result;
        Stack<TreeNode> toVisit = new Stack<>();
        toVisit.push(root);
        TreeNode cur;
        while (!toVisit.isEmpty()) {
            cur = toVisit.pop();
            result.add(cur.val); // 访问根节点
            if (cur.right != null) toVisit.push(cur.right); // 右节点入栈
            if (cur.left != null) toVisit.push(cur.left); // 左节点入栈
        }
        return result;
    }
}

中序遍历

递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        preorderHelper(root.left, result); // 递归遍历左子树
        result.add(root.val); // 访问根节点
        preorderHelper(root.right, result); //递归遍历右子树
    }
}

非递归

private List<Integer> inorderTraversalByIteration(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()){
        while (cur != null){
          	//左节点其实也就是子树的根节点
            stack.push(cur);
            cur = cur.left;
        }
        //从最底下的根节点开始，放入列表
        cur = stack.pop();
        res.add(cur.val);
        //然后拿到根节点的右子树，进行遍历
        cur = cur.right;
    }
    return res;
}

后序遍历

递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        preorderHelper(root.left, result); // 递归遍历左子树
        preorderHelper(root.right, result); //递归遍历右子树
        result.add(root.val); // 访问根节点
    }
}

非递归

后序非递归相对前两个遍历的非递归需要一个小技巧！

后序是 左 - 右 - 根，反过来就是根 - 右 - 左,那其实跟先序基本就一模一样了，先序是根 - 左 - 右，所以只需要在先序的非递归中改两行代码 + 加一行代码就完成了！

private List<Integer> postorderTraversalByIteration(TreeNode root){
    List<Integer> list = new ArrayList<>();
    TreeNode cur = root;
    Stack<TreeNode> stack = new Stack<>();
    while(cur != null || !stack.isEmpty()){
        while(cur != null){
            list.add(cur.val);
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop();
        cur = cur.left;
    }
    Collections.reverse(list);
    return list;
}

层序遍历

层序是不是还有一个名字叫 BFS

递归

这个竟然时间和空间击败了100%的人… 莫名有点开心啊

public List<List<Integer>> levelOrder(Node root) {
    if (root == null) return res;
    List<List<Integer>> res = new ArrayList<>();
    helper(root, 0, res);
    return res;
}
private void helper(Node root, int depth, List<List<Integer>> res) {
    if (root == null) return;
    //判断是否是新的一层
    if (depth + 1 > res.size()) {
        res.add(new ArrayList<>());
    }
    res.get(depth).add(root.val);

    //处理子节点
    for (Node node : root.children) {
        if (node != null) {
            helper(node, depth + 1, res);
        }
    }
}

非递归

上面讲了一种用队列实现的非递归思想

public static List<Integer> levelOrder(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if (root == null) return result;
    Queue<TreeNode> toVisit = new ArrayDeque<>();
    toVisit.add(root);
    TreeNode cur;
    while (!toVisit.isEmpty()) {
        cur = toVisit.poll();
        result.add(cur.val); // 访问根节点
        if (cur.left != null) toVisit.add(cur.left); // 左节点入队列
        if (cur.right != null) toVisit.add(cur.right); // 右节点入队列
    }
    return result;
}

/**
 * 非递归方法二，返回值不一样
 * @param root
 * @return
 */
public List<List<Integer>> levelOrderBy(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    TreeNode cur;
    while (!queue.isEmpty()) {
        List<Integer> list = new ArrayList<>();
        int pre_number = queue.size();
        while(pre_number > 0){
            cur = queue.poll();
            pre_number--;
            list.add(cur.val);
            if (cur.left != null){
                queue.add(cur.left); // 左节点入队列
            }
            if (cur.right != null) {
                queue.add(cur.right); // 右节点入队列
            }
        }
        res.add(list); 
    }
    return res;
}

相关题型

二叉树的右视图

题目

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路

层序遍历 BFS。先写出双重 list 的层序遍历，然后在每一个内层list中拿到最后一个值即可；
深度遍历 DFS。递归 DFS，从右向左，拿到第一个数即可。

实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<List<Integer>> lists = levelOrderBy(root);
        List<Integer> res = new ArrayList();
        for(List<Integer> list : lists){
            res.add(list.get(list.size()-1));
        }
        return res;
    }


public List<List<Integer>> levelOrderBy(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    TreeNode cur;
    while (!queue.isEmpty()) {
        List<Integer> list = new ArrayList<>();
        int pre_number = queue.size();
        while(pre_number > 0){
            cur = queue.poll();
            pre_number--;
            list.add(cur.val);
            if (cur.left != null){
                queue.add(cur.left); // 左节点入队列
            }
            if (cur.right != null) {
                queue.add(cur.right); // 右节点入队列
            }
        }
        res.add(list); 
    }
    return res;
}
}

class Solution {
  public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        solve(root, 0, res);
        return res;
    }

    public void solve(TreeNode root, int level, List<Integer> res) {
        if (root != null) {
            if (res.size() == level) {
                res.add(root.val);
            }
            solve(root.right, level + 1, res);
            solve(root.left, level + 1, res);
        }
    }
}

对称二叉树

题目

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

思路

先讲一下自己的思路: 利用层序非递归，用双层List存储树的节点，每一层存入一个单层List中，然后单层List可以采用二分判断是否对称！
答案思路：树的复制，这个想法很nice！复制原树，判断其左子树节点是否和右子树节点相同且判断其左子树的左是否等于右子树的右，左子树的右是否等于右子树的左。在非递归的写法中，树的复制这种思想体现的更加明显，这个就是典型的用空间换时间！

实现

树复制思想之递归

/**
    * 对称二叉树 递归做法
    * 我的想法是使用层序遍历，找到对称点，每一层判断完即可！
    * 结果是没写出来
    * 看了答案是自己跟自己镜像比较，太妙了！！
    * @param root
    * @return
    */
   private static boolean isSymmetricByRecursion(TreeNode root){
       if (root == null) return true;
       return helper(root.left,root.right);
   }

   /**
    * 递归三部曲
    * 1、确定递归出口，当节点为空时，即无需再递归
    * 2、确定返回值，返回值为boolean，判断当前
    * 3、镜像嘿嘿，这个想法很nice
    * @param tree1
    * @param tree2
    * @return
    */
   private static boolean helper(TreeNode tree1, TreeNode tree2) {
       //判断是否是新的一层
       if(tree1 == null && tree2 == null){
           return true;
       }
       else if(tree1 == null || tree2 == null){
           return false;
       }
       else {
           return tree1.val == tree2.val && helper(tree1.left,tree2.right) && helper(tree1.right,tree2.left);
       }
   }

树复制之非递归

Tip: 在复现非递归时，发现一个问题，就是Queue的实现类ArrayDeque是非线程安全的，但是其不允许存储null元素，这个跟ArrayList、LinkedList、HashMap、TreeMap等非线程安全的集合不同！！！！因为系统根据某个位置是否为null来判断元素的存在，null插入直接会报空指针异常。[ArrayDeque当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。]

所以这里使用了Queue的另外一个实现类LinkedList，它也是非线程安全的哟，但是可以存储null！！！

private static boolean isSymmetricByIteration(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<>();
    if(root == null) return true;
    queue.add(root.left);
    queue.add(root.right);
    while(!queue.isEmpty()){
        TreeNode tree1 = queue.poll();
        TreeNode tree2 = queue.poll();
        if(tree1 == null && tree2 == null ) continue;
        if(tree1 == null || tree2 == null) return false;
        if(tree1.val != tree2.val) return false;
        queue.add(tree1.left);
        queue.add(tree2.right);
        queue.add(tree1.right);
        queue.add(tree2.left);
    }
    return true;
}

层序非递归

/**
     * 迭代
     * @param root
     * @return
     */
    private static boolean isSymmetricByLevel(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode cur;
        //得到双层list
        while (!queue.isEmpty()) {
            List<Integer> list = new LinkedList<>();
            int pre_number = queue.size();
            System.out.println(pre_number);
            while(pre_number > 0 ){
                cur = queue.poll();
                pre_number--;
                if(cur == null) {
                    list.add(null);
                    continue;
                }
                list.add(cur.val);
                if (cur.left != null){
                    queue.add(cur.left); // 左节点入队列
                }
                else{
                    queue.add(null);
                }
                if (cur.right != null) {
                    queue.add(cur.right); // 右节点入队列
                }
                else{
                    queue.add(null);
                }
            }
            res.add(list);
        }
        //对每一层list进行判断，看是否是对称的，可以使用dp
        for(List list:res){
            int size = list.size();
            for(int i = 0;i < size/2;i++){
                if(list.get(i) != list.get(size-1-i)){
                    return false;
                }
            }
        }
        return true;
    }

二叉树的最大深度

吖！这个是二叉树最简单的题目了吧…但是绝对是一道经典好题！下面将用最常用的三种方法解决它！

题目

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，
    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

思路

方法一：递归。这个我在另外一篇递归中的文章中有提到，可以一行代码解决哟！
方法二：层序遍历。即用BFS解决，每遍历完一层就记录深度。
方法三：DFS。用栈实现即可。(还学到Pair这玩意…为何我以前都不知道)

实现

递归
- 1、找出口，节点为空即可退出递归。
- 2、找返回值，返回的是该节点所在层的深度。
- 3、确定一次递归需要做什么。当前节点深度 = 子节点最大深度 + 1。

class Solution {
    public int maxDepth(TreeNode root) {
       return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

层序非递归遍历，稍微改写一下就好了，这里不需要存储节点，所以只需要用一个值来记录深度即可。

第一种非递归方式改写

import javafx.util.Pair;
class Solution {
    public int maxDepth(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) return 0;
        Queue<Pair<TreeNode,Integer>> toVisit = new ArrayDeque<>();
        toVisit.add(new Pair<>(root,1));
        Pair<TreeNode,Integer> cur;
        int max_depth = 0;
        while (!toVisit.isEmpty()) {
            cur = toVisit.poll();
            int depth = cur.getValue();
            max_depth = Math.max(max_depth,depth);
            if (cur.getKey().left != null) toVisit.add(new Pair<>(cur.getKey().left,depth + 1)); // 左节点入队列
            if (cur.getKey().right != null) toVisit.add(new Pair<>(cur.getKey().right,depth + 1)); // 右节点入队列
        }
        return max_depth;
    }
}

第二种非递归方式改写

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        //        List<List<Integer>> res = new ArrayList<>(); //这里无需存储节点，只需记录深度即可
        int depth = 0;
        if (root == null) return depth;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        TreeNode cur;
        while (!queue.isEmpty()) {
//            List<Integer> list = new ArrayList<>();
            int pre_number = queue.size();
            while(pre_number > 0){
                cur = queue.poll();
                pre_number--;
//                list.add(cur.val); //这里可以不用加入列表
                if (cur.left != null){
                    queue.add(cur.left); // 左节点入队列
                }
                if (cur.right != null) {
                    queue.add(cur.right); // 右节点入队列
                }
            }
//            res.add(list);
            depth++;
        }
//        return res.size();
        return depth;
    }
}

其实就是在先序非递归的基础上稍加改动，压栈的不再只是节点，还包括了节点的深度，用Pair类型存储！

尝试了用Map类型存储，发现行不通…因为拿不到栈顶的节点！

import javafx.util.Pair;
class Solution {
    public int maxDepth(TreeNode root) {
        //得用一个栈来进行处理
        Stack<Pair<TreeNode,Integer>> stack = new Stack<>();
        TreeNode cur = root;
        int depth= 0;
        int MaxDepth = 0;
        while(cur != null || !stack.isEmpty()){
            while (cur != null){
                //左节点其实也就是子树的根节点
                depth++;
                stack.push(new Pair<>(cur,depth));
                cur = cur.left;
            }
            //然后拿到根节点的右子树，进行遍历
            Pair<TreeNode,Integer> top = stack.pop();
            depth = top.getValue();
            MaxDepth = Math.max(depth,MaxDepth);
            cur = top.getKey().right;
        }
        return MaxDepth;
    }
}

二叉树的最小深度

题目

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2。

思路

BFS，套用 BFS 模板。

代码

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        LinkedList<TreeNode> queue = new LinkedList();
        queue.add(root);
        int depth = 1;
        while(!queue.isEmpty()){
            int sz = queue.size();
            for(int i = 0;i < sz;i++){
                TreeNode cur = queue.poll();
                if(cur.left == null && cur.right == null){
                    return depth;
                }
                if(cur.left != null){
                    queue.add(cur.left);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                }
            }
            depth++;
        }
        return depth;

    }
}

路径总和「根到叶子节点」是否等于目标和

题目

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路

递归。我都递归的要吐了，二叉树日常递归！
DFS，自己建栈模拟递归。

实现

递归 1

（三元表达式纯粹装逼哈哈哈）

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        return root == null ? false : hasPathSumByRecursion(root,0,sum);
    }
    private boolean hasPathSumByRecursion(TreeNode root, int total, int sum) {
        if(root == null) return false;
        total = total + root.val;
        return (root.left == null && root.right == null) ? total == sum : hasPathSumByRecursion(root.left,total,sum) || hasPathSumByRecursion(root.right,total,sum);
    }
}

递归 2

public boolean hasPathSum(TreeNode root,int sum){
    if(root == null) return false;
    sum-=root.val;
    if(root.left == null && root.right == null){
        return sum == 0;
    }
    return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
}

我觉得思想都很简单啊，其实二叉树的基本上所有的题目都是建立在前序和层序遍历的基础上的，熟练掌握了前序和层序的递归非递归就基本能解所有题目了…

(在前序非递归的基础上稍加改动就行了…)

import javafx.util.Pair;
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        Stack<Pair<TreeNode,Integer>> toVisit = new Stack<>();
        toVisit.push(new Pair<>(root,root.val));
        while (!toVisit.isEmpty()){
            Pair<TreeNode,Integer> cur = toVisit.pop();
            if (cur.getKey().right != null) toVisit.push(new Pair<>(cur.getKey().right,cur.getValue()+cur.getKey().right.val)); // 右节点入栈
            if (cur.getKey().left != null) toVisit.push(new Pair<>(cur.getKey().left,cur.getValue()+cur.getKey().left.val)); // 左节点入栈
            if(cur.getKey().left == null && cur.getKey().right == null && cur.getValue() == sum) return true;
        }
        return false;
    }
}

求根节点到叶节点数字之和

题目

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的所有数字之和。

叶节点 是指没有子节点的节点。

示例1 示例2

思路

dfs：从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历
- 时间复杂度 O(n)，n为二叉树节点个数
- 空间复杂度 O(n)，最坏情况下，二叉树高度等于节点个数，递归深度最多为 n
bfs：需要维护两个队列，分别存储节点和节点对应的数字。
- 初始时，将根节点和根节点的值分别加入两个队列。每次从两个队列分别取出一个节点和一个数字，进行如下操作：
- 如果当前节点是叶子节点，则将该节点对应的数字加到数字之和；
- 如果当前节点不是叶子节点，则获得当前节点的非空子节点，并根据当前节点对应的数字和子节点的值计算子节点对应的数字，然后将子节点和子节点对应的数字分别加入两个队列。
- 搜索结束后，即可得到所有叶子节点对应的数字之和。
- 时间复杂度 O(n)，同 dfs
- 空间复杂度 O(n)，取决于队列长度，队列元素个数不会超过 n

代码

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int prevSum) {
        if (root == null) {
            return 0;
        }
        int sum = prevSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        } else {
            return dfs(root.left, sum) + dfs(root.right, sum);
        }
    }
}

class Solution {
    public int sumNumbers(TreeNode root) {
        return bfs(root);
    }



    private int bfs(TreeNode root){
        Queue<TreeNode> queue = new LinkedList();
        Queue<Integer> sumQueue = new LinkedList();
        int sum = 0;
        queue.offer(root);
        sumQueue.add(root.val);
        while(!queue.isEmpty()){
            int sz = queue.size();
            for(int i = 0;i < sz;i++){
                TreeNode cur = queue.poll();
                Integer num = sumQueue.poll();
                if(cur.left == null && cur.right == null){
                    sum+=num;
                }
                if(cur.left != null){
                    queue.add(cur.left);
                    sumQueue.add(cur.left.val + 10 * num);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                    sumQueue.add(cur.right.val + 10 * num);
                }
            }
        }
        return sum;
    }
}

求从根节点到叶子节点的最大值

题目

二叉树从根节点到叶子节点的最长路径

思路

上题稍微改一下就好啦，加个 max，记录一下。

代码

public static void main(String[] args) {
    TreeNode root = new TreeNode(5);
    root.left = new TreeNode(4);
    root.right = new TreeNode(8);

    root.left.left = new TreeNode(11);
    root.right.left = new TreeNode(13);
    root.right.right = new TreeNode(4);

    root.left.left.left = new TreeNode(7);
    root.left.left.right = new TreeNode(2);
    root.right.right.right = new TreeNode(1);


    int res = getMaxPathSumByRecursion(root,0);
    System.out.println(res);
}
/**
 * 求二叉树从根节点到叶子节点的最大路径
 */
private static int max = Integer.MIN_VALUE;
private static int getMaxPathSumByRecursion(TreeNode root, int total) 		{
    if(root == null) return 0;
    total = total + root.val;
    if(root.left == null && root.right == null){
        max = Math.max(max,total);
    }
    else{
        getMaxPathSumByRecursion(root.left,total);
        getMaxPathSumByRecursion(root.right,total);
    }
    return max;
}

二叉树的直径

题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :
给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

思路

按照常用方法计算一个节点的深度：max(depth of node.left, depth of node.right) + 1。在计算的同时，经过这个节点的最大直径为 (depth of node.left) + (depth of node.right) 。搜索每个节点并记录这些路径经过的点数最大值，期望长度是就是结果。

代码

class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 0;
        //拿到每个节点的左右子树的深度的和，ans代表了最长直径，其实也就是最大的左右子树深度之和
        depth(root);
        return ans;
    }
    public int depth(TreeNode node) {
        if (node == null) return 0;
        int L = depth(node.left);
        int R = depth(node.right);
        ans = Math.max(ans, L+R);
        return Math.max(L, R) + 1;
    }
}

二叉树的最大路径和

题目

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

思路

这题还是挺难的，要求最大路径和，可以采用递归，递归就是三部曲：

1、确定递归出口，这个简单，root == null 即退出

2、确定返回值，这个是本题最难的，返回的是以该节点结尾的最大路径和！！！

3、一级递归需要做的事，其实就是去算最大的路径和，这个很简单，在二叉树中，一级递归其实也就是三个节点，分别是根节点，左子树节点，右子树节点，既然每个节点返回的是以该节点结尾的最大路径和，则我们可以在每级递归时去更新一下最大的路径和，即左子树节点返回来的以其节点结尾的最大路径和 + 根节点的值 + 右子树节点返回的以该节点结尾的最大路径和。

代码

class Solution {
  int max_sum = Integer.MIN_VALUE;

  public int max_gain(TreeNode node) {
    if (node == null) return 0;

    // max sum on the left and right sub-trees of node
    int left_gain = Math.max(max_gain(node.left), 0);
    int right_gain = Math.max(max_gain(node.right), 0);

    // the price to start a new path where `node` is a highest node
    int price_newpath = node.val + left_gain + right_gain;

    // update max_sum if it's better to start a new path
    max_sum = Math.max(max_sum, price_newpath);

    // for recursion :
    // return the max gain if continue the same path
    return node.val + Math.max(left_gain, right_gain);
  }

  public int maxPathSum(TreeNode root) {
    max_gain(root);
    return max_sum;
  }
}

从中序与后序遍历序列构造二叉树

题目

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

1 2	中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

思路

我写的应该比较简洁，参数少的原因是抓住了后序是左--右--根的特点，所以后序遍历从后向前是根--右--左，故在递归时根本没有必要将后序遍历的数组界限传入，每次有节点加入就自减一就行，只要满足了先拿到根节点然后遍历右子树，再遍历左子树这个原则就Okay。

至于递归如何写，其实把握三个原则就行：

递归出口，这里就不解释了
每次递归的返回值，这里很明显就是题目要求的root节点
单次递归需要做的事，我们需要构建一个树，那么单次递归就是拿到根节点，并且指向正确的左右子树即可。

代码

class Solution {
    int index;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder,int[] postorder){
        index = inorder.length - 1;
        for(int i = 0;i <= index; i++){
            map.put(inorder[i],i);
        }
        return buildTreeByRecursion(inorder,postorder,0,index);
    }

    private TreeNode buildTreeByRecursion(int[] inorder,int[] postorder,int inorder_start,int inorder_end){
        if(inorder_start > inorder_end) return null;
        //先拿到根节点的值,确定其在中序遍历的位置，并且将其后序遍历的索引值的末尾往前一位
        int inorder_root = map.get(postorder[index]);
        TreeNode root = new TreeNode(postorder[index--]);
        //然后确定左右子树，并且递归即可
        // 注意哦！是必须先递归右子树，再递归左子树，因为后序是左右根的顺序，后序末尾自减一，此时应该是右子树的根节点！
        // 所以必须全部右子树构建完成再去构建左子树
        root.right = buildTreeByRecursion(inorder,postorder,inorder_root + 1,inorder_end);
        root.left =  buildTreeByRecursion(inorder,postorder,inorder_start,inorder_root - 1);
        return root;
    }
}

从前序与中序遍历序列构造二叉树

题目

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

1 2	前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

思路

跟上面的思路一致，就是刚好相反而已嘛…

代码

class Solution {
    int pre = 0;
    Map<Integer,Integer> pre_in_map = new HashMap<>();
    public TreeNode buildTree(int[] preorder,int[] inorder){
        int inorder_end = inorder.length - 1;
        for(int i = 0;i <= inorder_end; i++){
            pre_in_map.put(inorder[i],i);
        }
        return buildTreeByRecursion(preorder,inorder,0,inorder_end);
    }
    private TreeNode buildTreeByRecursion(int[] preorder,int[] inorder,int inorder_start,int inorder_end){
        if(inorder_start > inorder_end) return null;
        //先拿到根节点的值,确定其在中序遍历的位置，并且将先序遍历的索引值的开始值向前一位
        int inorder_root = pre_in_map.get(preorder[pre]);
        TreeNode root = new TreeNode(preorder[pre++]);
        //然后确定左右子树，并且递归即可
        // 注意哦！是必须先递归左子树，再递归右子树，因为先序是根左右的顺序
        // 所以必须全部左子树构建完成再去构建右子树
        root.left =  buildTreeByRecursion(preorder,inorder,inorder_start,inorder_root - 1);
        root.right = buildTreeByRecursion(preorder,inorder,inorder_root + 1,inorder_end);
        return root;
    }
}

填充每个节点的下一个右侧节点指针

题目

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例：

思路

最简单的思路：层序遍历，分别获得每层的节点，然后生成链表，所以这个不是完美二叉树也可以做，也就是说没有用到 完全二叉树 的性质！所以必定不是最优解！而且这个使用的不是常量级的空间，其实是不太符合要求的。
(看了答案的)高赞的 拉拉链解法，将一棵大的二叉树一分为二，处理两棵小二叉树的连接，再递归解决小二叉树内部连接。
还有一种非递归的方法，个人觉得也是非常的精妙，之前我们是用列表保存每一层的节点，其实这是一种浪费。只需要解决三个问题就够了。参考网址
- 每一层怎么遍历？
  之前是用队列将下一层的节点保存了起来。
  
  这里的话，其实只需要提前把下一层的next构造完成，到了下一层的时候就可以遍历了。
- 什么时候进入下一层？
```
之前是得到当前队列的元素个数，然后遍历那么多次。
```
这里的话，注意到最右边的节点的next为null，所以可以判断当前遍历的节点是不是null。
- 怎么得到每层开头节点？
  之前队列把当前层的所以节点存了起来，得到开头节点当然很容易。
  
  这里的话，我们额外需要一个变量把它存起来。
三个问题都解决了，就可以写代码了。利用三个指针，start指的是当前层的最左节点，也就是本层的起点，cur指的是当前正在遍历的节点，cur.next指的是正在遍历的节点的下一个节点！我觉得这个方法最难想的就是 在遍历本层的时候，将下层的next构造完成！！！

代码

方法一：层序遍历

/**
 * 层序遍历
 * @param root
 * @return
 */
public Node connect1(Node root) {
    if (root == null) {
        return root;
    }
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node pre = null;
        for (int i = 0; i < size; i++) {
            Node cur = queue.poll();
            //从第二个节点开始，将前一个节点的 pre 指向当前节点
            if (i > 0) {
                pre.next = cur;
            }
            pre = cur;
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    return root;
}

方法二：拉拉链法

/**
 * 方法二 拉拉链法
 * @param root
 * @return
 */
public Node connect2(Node root){
    if(root == null) return null;
    Node left = root.left;
    Node right = root.right;
    while(left != null){
        left.next = right;
        left = left.right;
        right = right.left;
    }
    connect1(root.left);
    connect1(root.right);
    return root;
}

方法三：非递归解法（个人最推荐的做法）

/**
 * 非递归解法，这个应该是最符合题意的解法
 * @param root
 * @return
 */
public Node connect3(Node root){
    if(root == null) return null;
    Node start = root;
    while(start.left != null){
        Node cur = start;
        while(cur != null){
            cur.left.next = cur.right;
            if(cur.next != null) cur.right.next = cur.next.left;
            cur = cur.next;
        }
        start = start.left;
    }
    return root;
}

填充每个节点的下一个右侧节点指针 II

题目

给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

1
2
3

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

树中的节点数小于 6000
-100 <= node.val <= 100

思路

方法一：上一题已经讲过，依旧可以用上面的代码，BFS。

方法二：题目要求只能使用常量级额外空间，意味着其实严格上不能使用队列，那怎么做呢？

可以使用一个尾指针，将所有的节点连接起来，刚好就是题目的next指针，可以做到这一点，至于每一层如何开始，只需要再引入一个指针进行标记即可，不同于BFS的是，BFS在遍历当前层时，是处理当前层的横向连接，并且将子节点加入队列中以便下一次的遍历，而方法二则是在每次循环时，直接处理下一层节点的横向连接问题，因为我并不知道每一层的节点数量和具体位置(无法保存)，只能是如果该层下的子节点存在，就将他们连接！

cur 指针利用 next 不停的遍历当前层。

如果 cur 的孩子不为 null 就将它接到 tail 后边，然后更新tail。

当 cur 为 null 的时候，再利用 dummy 指针得到新的一层的开始节点。

dummy 指针在链表中经常用到，他只是为了处理头结点的情况，它并不属于当前链表。

作者：windliang
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-28/
来源：力扣（LeetCode）

代码

方法一：同上(略)
方法二：

public Node connectII(Node root){
    if(root == null) return null;
    Node cur = root; //遍历的当前节点
    Node tail; //中间节点，起承接的作用
    while(cur != null){
        //遍历整棵树
        //注意这里的start应该是一个链表头结点，其指向的next为当前层的下一层的第一个节点
        Node start = new Node();
        tail = start;
        //遍历当前层
        while(cur != null){
            if(cur.left != null){
                tail.next = cur.left;
                tail = tail.next;
            }
            if(cur.right != null){
                tail.next = cur.right;
                tail = tail.next;
            }
            cur = cur.next;
        }
        cur = start.next;
    }
    return root;
}

二叉树的最近公共祖先

题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

1
2
3

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

1
2
3

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

思路

注意p,q必然存在树内, 且所有节点的值唯一！！！
递归思想，对以root为根的(子)树进行查找p和q，如果root == null || p || q 直接返回root
表示对于当前树的查找已经完毕，否则对左右子树进行查找，根据左右子树的返回值判断:

左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA
如果左右子树返回值只有一个不为null, 说明只有p和q存在于左或右子树中, 最先找到的那个节点为LCA
左右子树返回值均为null, p和q均不在树中, 返回null

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root)return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left!=null && right != null)return root;
        return left == null ? right : left;
    }
}

二叉树的序列化与反序列化

题目

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

思路

这题做了两个小时…还没整出来…思路其实特别的简单，就是用层序遍历，将所有结点存入列表中（包括了空节点），然后转成字符串，字符串再转成列表然后建立树

卡在建立树这块…心态有点炸…冷静会

代码

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        Queue<String> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        res.offer(String.valueOf(root.val));
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 有左节点就插入左节点，没有就插入null
            if (node.left != null) {
                queue.offer(node.left);
                res.offer(String.valueOf(node.left.val));
            } else {
                res.offer("null");
            }
            // 有右节点就插入右节点，没有就插入null
            if (node.right != null) {
                queue.offer(node.right);
                res.offer(String.valueOf(node.right.val));
            } else {
                res.offer("null");
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while(!res.isEmpty()) {
            sb.append(res.poll());
            if (!res.isEmpty()) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        data = data.substring(1, data.length()-1);
        if (data.length() == 0) {
            return null;
        }
        Queue<String> ls = new LinkedList<>(Arrays.asList(data.split(",")));
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = null;
        while(!ls.isEmpty()) {
            String res = ls.poll();
            // 创建根节点
            if (root == null) {
                root = new TreeNode(Integer.valueOf(res));
                queue.offer(root);
                continue;
            }
            // 注意：ls的长度总是奇数的，所以除了根节点，其余节点创建时可以一次取两个ls中的元素
            TreeNode father = queue.poll();
            // 创建左节点
            if (!res.equals("null")) {
                TreeNode curr = new TreeNode(Integer.valueOf(res));
                father.left = curr;
                queue.offer(curr);
            }
            // 创建右节点
            res = ls.poll();
            if (!res.equals("null")) {
                TreeNode curr = new TreeNode(Integer.valueOf(res));
                father.right = curr;
                queue.offer(curr);
            }
        }
        return root;
    }
}

翻转二叉树

题目

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4   
   /   \
  7     2
 / \   / \
9   6 3   1

思路

递归…注释有说

代码

/**
 * 递归三部曲
 * 1、找到出口，节点为空即为出口
 * 2、找到返回值，返回值，返回值应该是子树的根节点
 * 3、一次递归需要做啥，需要将左右子树翻转，现在我们手上也就是三个节点
 * 分别是根节点，左子树根节点，右子树根节点，要做的就只是左右子树根节点翻转即可
 * @param root
 * @return
 */
private static TreeNode invertTree(TreeNode root){
    if(root == null) return null;
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

合并二叉树

题目

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
			Tree 1                    Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

注意: 合并必须从两个树的根节点开始。

思路

使用递归。我们可以对这两棵树同时进行前序遍历，并将对应的节点进行合并。在遍历时，如果两棵树的当前节点均不为空，我们就将它们的值进行相加，并对它们的左孩子和右孩子进行递归合并；如果其中有一棵树为空，那么我们返回另一颗树作为结果；如果两棵树均为空，此时返回任意一棵树均可（因为都是空）。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

验证二叉搜索树

题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

思路

中序遍历

代码

class Solution {
  public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    double inorder = - Double.MAX_VALUE;

    while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
      if (root.val <= inorder) return false;
      inorder = root.val;
      root = root.right;
    }
    return true;
  }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

把二叉搜索树转换为累加树

题目

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree

思路

二叉搜索树，第一想法就是用中序递归去做，累加树的意思是根节点的值 = 根节点的值 + 右子树的值，然后再更新左子树的值 = 根节点的值 + 左子树的值，所以就符合右中左的遍历顺序，只要写出来右中左的递归，然后用一个全局变量记录上一个遍历的节点的值再加上本身的值，就okay了！

代码

class Solution {
    int add = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        convertBST(root.right);
        root.val += add;
        add = root.val;
        convertBST(root.left);
        return root;
    }
}

Tip: 其实个人觉得这个题目有问题，既然是累加树，为何是按照右中左的遍历顺序来累加呢…我的根节点还得加到我左子树的最右叶子节点上！真的荒唐啊…

二叉树展开为链表

题目

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

将其展开为：

思路

注意题目的要求是 原地 展开！

这里强推一手题解里一位大佬写的！总共3个大方法，非常好！！！

二叉树转换成链表

解法一[自顶向下非递归]

可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似。

将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点

代码的话也很好写，首先我们需要找出左子树最右边的节点以便把右子树接过来。

public void flatten(TreeNode root) {
    while (root != null) { 
        //左子树为 null，直接考虑下一个节点
        if (root.left == null) {
            root = root.right;
        } else {
            // 找左子树最右边的节点
            TreeNode pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            } 
            //将原来的右子树接到左子树的最右边节点
            pre.right = root.right;
            // 将左子树插入到右子树的地方
            root.right = root.left;
            root.left = null;
            // 考虑下一个节点
            root = root.right;
        }
    }

解法二[自顶向上，推荐]

题目中，要求说是 in-place，之前一直以为这个意思就是要求空间复杂度是 O(1)。偶然看见评论区大神的解释， in-place 的意思可能更多说的是直接在原来的节点上改变指向，空间复杂度并没有要求。所以这道题也可以用递归解一下。利用变形的后序遍历 右左根即可。

private TreeNode pre = null;

public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.right);
    flatten(root.left);
    root.right = pre;
    root.left = null;
    pre = root;
}

相应的左孩子也要置为 null，同样的也不用担心左孩子丢失，因为是后序遍历，左孩子已经遍历过了。和 112 题一样，都巧妙的利用了后序遍历。

既然后序遍历这么有用，利用 112 题介绍的后序遍历的迭代方法，把这道题也改一下吧。

public void flatten(TreeNode root) { 
    Stack<TreeNode> toVisit = new Stack<>();
    TreeNode cur = root;
    TreeNode pre = null;

    while (cur != null || !toVisit.isEmpty()) {
        while (cur != null) {
            toVisit.push(cur); // 添加根节点
            cur = cur.right; // 递归添加右节点
        }
        cur = toVisit.peek(); // 已经访问到最右的节点了
        // 在不存在左节点或者右节点已经访问过的情况下，访问根节点
        if (cur.left == null || cur.left == pre) {
            toVisit.pop(); 
            /**************修改的地方***************/
            cur.right = pre;
            cur.left = null;
            /*************************************/
            pre = cur;
            cur = null;
        } else {
            cur = cur.left; // 左节点还没有访问过就先访问左节点
        }
    } 
}

解法三[自顶向上]

解法二中提到如果用先序遍历的话，会丢失掉右孩子，除了用后序遍历，还有没有其他的方法避免这个问题。在 Discuss 又发现了一种解法。

为了更好的控制算法，所以我们用先序遍历迭代的形式，正常的先序遍历代码如下，

public static void preOrderStack(TreeNode root) {
    if (root == null) { 
        return;
    }
    Stack<TreeNode> s = new Stack<TreeNode>();
    while (root != null || !s.isEmpty()) {
        while (root != null) {
            System.out.println(root.val);
            s.push(root);
            root = root.left;
        }
        root = s.pop();
        root = root.right;
    }
}

还有一种特殊的先序遍历，提前将右孩子保存到栈中，我们利用这种遍历方式就可以防止右孩子的丢失了。由于栈是先进后出，所以我们先将右节点入栈。

public static void preOrderStack(TreeNode root) {
    if (root == null){
        return;
    }
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(root);
    while (!s.isEmpty()) {
        TreeNode temp = s.pop();
        System.out.println(temp.val);
        if (temp.right != null){
            s.push(temp.right);
        }
        if (temp.left != null){
            s.push(temp.left);
        }
    }
}

之前我们的思路如下：

题目其实就是将二叉树通过右指针，组成一个链表。

1	1 -> 2 -> 3 -> 4 -> 5 -> 6

我们知道题目给定的遍历顺序其实就是先序遍历的顺序，所以我们可以利用先序遍历的代码，每遍历一个节点，就将上一个节点的右指针更新为当前节点。

先序遍历的顺序是 1 2 3 4 5 6。

遍历到 2，把 1 的右指针指向 2。1 -> 2 3 4 5 6。

遍历到 3，把 2 的右指针指向 3。1 -> 2 -> 3 4 5 6。

因为我们用栈保存了右孩子，所以不需要担心右孩子丢失了。用一个 pre 变量保存上次遍历的节点。修改的代码如下：

public void flatten(TreeNode root) { 
    if (root == null){
        return;
    }
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(root);
    TreeNode pre = null;
    while (!s.isEmpty()) {
        TreeNode temp = s.pop(); 
        /***********修改的地方*************/
        if(pre!=null){
            pre.right = temp;
            pre.left = null;
        }
        /********************************/
        if (temp.right != null){
            s.push(temp.right);
        }
        if (temp.left != null){
            s.push(temp.left);
        } 
        /***********修改的地方*************/
        pre = temp;
        /********************************/
    }
}

总结

解法一和解法三可以看作自顶向下的解决问题，解法二可以看作自底向上。以前觉得后序遍历比较麻烦，没想到竟然连续遇到了后序遍历的应用。先序遍历的两种方式自己也是第一次意识到，之前都是用的第一种正常的方式。

作者：windliang
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/

Tips: 这个大佬写的是真好！

深度和广度优先搜索

BFS

框架

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

队列 q 存储当前需要遍历的节点，BFS 的核心数据结构；cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。