二叉树遍历-力扣题解

第一部分介绍二叉树的三种遍历、要达到默写水平；第二部分力扣二叉树小卡片的几乎所有题目；

第三部分剑指offer上面几道经典的题；第四部分是不那么简单的总结；

[1]部分代码思想参考了开源项目github.com/greyireland/algorithm-pattern

[2]题目基本来源力扣学习小卡片《二叉树》https://leetcode-cn.com/leetbook/detail/data-structure-binary-tree/

1 二叉树的遍历

二叉树的增删改查的前提都是遍历找到某一个结点，所以遍历是二叉树的基本功（至少想要做的了题是这样），遍历分为三类：

二叉树的递归遍历
二叉树的非递归遍历（借用栈）
二叉树BFS的层次遍历（借用队列）

先建一个结点类，搭建二叉树的环境，类中含一个按结点值大小插入成二叉搜索树的函数insertIntoBST，节点类放在Main类的外面即可，不要加public

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public TreeNode insertIntoBST(TreeNode root, int val){
        if (root==null) return new TreeNode(val);
        if (root.val>=val){
            if(root.left==null) root.left = new TreeNode(val);
            else this.insertIntoBST(root.left,val);
        }else{
            if(root.right==null) root.right = new TreeNode(val);
            else this.insertIntoBST(root.right,val);
        }
        return root;
    }
    
}

1.1 递归遍历

108. 将有序数组转换为二叉搜索树

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

ACM模式一般需要自己建立二叉树，这里给出用有序数组建立一个平衡的二叉搜索树的递归代码（直接写在主类中作为一个静态方法，mian方法里面调用之）

private static TreeNode helper(int[] nums, int left, int right){
    if(left>right) return null;
    int mid = left + (right-left)/2;
    TreeNode root = new TreeNode(nums[mid]);
    TreeNode leftNode = helper(nums, left, mid-1);
    TreeNode rightNode = helper(nums,mid+1,right);
    root.left = leftNode;
    root.right = rightNode;
    return root;
}

为更具一般性，我这里遍历时统一将元素放在list数组中。想要存入数组中，需要在调用前新建res集合，每次调用时作为参数传递

//前序遍历
List<Integer> resPre = new ArrayList<>();
preorderTraversal(root,resPre);

//中序遍历
List<Integer> resIn = new ArrayList<>();
inorderTraversal(root,resIn);

//后序遍历
List<Integer> resPost = new ArrayList<>();
postorderTraversal(root,resPost);

1前序遍历

// 递归 前序遍历
private static void preorderTraversal(ListNode root,List<Integer> res){
    if(root == null) return;
    res.add(root.val);
    preorderTraversal(root.left,res);
    preorderTraversal(root.right,res);
}

2中序遍历

// 递归 中序遍历
private static void inorderTraversal(ListNode root,List<Integer> res){
    if(root == null) return;
    inorderTraversal(root.left,res);
    res.add(root.val);
    inorderTraversal(root.right,res);
}

3后续遍历

// 递归 后序遍历
private static void postorderTraversal(ListNode root,List<Integer> res){
    if(root == null) return;
    postorderTraversal(root.left,res);
    postorderTraversal(root.right,res);
    res.add(root.val);
}

1.2 非递归遍历（stark）

List<Integer> res1 = preorderTraversal(root);

List<Integer> res2 = inorderTraversal(root);

List<Integer> res3 = postorderTraversal(root);

1前序遍历

我画了一下迭代过程，过程有点像深度优先搜索，跟下面这个经典的回溯很像、只是选择集合变成了二叉树。

先把所有的left结点存入结果集，根结点先进结果集、同时也存入栈中，
然后一个一个的出栈，看出栈的结点有没有right结点，
有的话以该结点为root，同样的方式进行搜索、进结果集。

//非递归 前序遍历stack
private static List<Integer> preorderTraversal(ListNode root){
    if(root == null) return new ArrayList<>(0);
    List<Integer> res = new ArrayList<>();
    Deque<ListNode> stack = new LinkedList<>();
    while(root!=null || !stack.isEmpty()){
        while(root!=null){
            res.add(root.val);
            stack.push(root);
            root = root.left;
        }
        //stack弹出 最后进入也就是最左子结点
        ListNode tempNode = stack.pop();
        root = tempNode.right;
    }
    return res;
}

2中序遍历

中序遍历与前序遍历的差别就是：先把元素存入栈中，元素从栈中弹出后再加入到结果集res中，也就是先把最左边的加入结果集

//非递归 中序遍历stack
private static List<Integer> inorderTraversal(ListNode root){
    if(root==null) return new ArrayList<>(0);
    List<Integer> res = new ArrayList<>();
    Deque<ListNode> stack = new LinkedList<>();
    while(root!=null ||  !stack.isEmpty()){
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        ListNode tempNode = stack.pop();
        res.add(tempNode.val);
        root = tempNode.right;
    }
    return  res;
}

3后序遍历

因为栈中的元素始终是先左再右的，对后序遍历麻烦一些。要保证根节点必须要在右结点弹出之后再弹出，所以通过设置lastVisit结点来标识右子节点是否已经弹出，即弹出之前多加一层判断，看当前结点的right是否为空或者是否上次已弹出

//非递归 后续遍历stack root必须要在right弹出之后再弹出
// 通过lastVisit标识右子节点是否已经弹出
private static List<Integer> postorderTraversal(ListNode root){
    if(root == null) return null;
    ListNode lastVisited = null;
    List<Integer> res = new ArrayList<>();
    Deque<ListNode> stack = new LinkedList<>();
    while(root!=null ||!stack.isEmpty()){
        while(root!=null) {
            stack.push(root);
            root = root.left;
        }
        //先看看能不能弹出
        ListNode tempNode = stack.peek();
        //多一层判断
        if(tempNode.right==null||tempNode.right==lastVisited){
            stack.pop();
            res.add(tempNode.val);
            lastVisited = tempNode; //标记已经加入结果
        }else{
            root = tempNode.right;
        }
    }
    return res;
}

1.3 层序遍历

102. 二叉树的层序遍历

107. 二叉树的层序遍历 II

层序遍历利用队列的先进先出的特性，队列一次存入每一层的所有元素、然后一次循环一次性弹出该层的所有元素加入临时list集合中，弹出的过程中、顺手将下一次的元素入队，每次循环结束、将临时list集合加入二维结果集res中。

层序遍历的考察点挺多的，比较重要，是基本功。

//层序遍历
private static List<List<Integer>> levelOrderTraversal(ListNode root){
    if(root==null) return null;
    List<List<Integer>> res = new ArrayList<>();
    ArrayDeque<ListNode> deque = new ArrayDeque<>();
    deque.add(root);
    while(!deque.isEmpty()){
        //取队列的长度 也就是当前层有多少的元素、便于循环
        int length = deque.size();
        List<Integer> leverList = new ArrayList<>(); //保存每层元素的集合
        for(int i=0;i<length;++i){
            ListNode leverNode = deque.poll();
            leverList.add(leverNode.val);
            //下一次元素入队
            if(leverNode.left!=null) deque.offer(leverNode.left);
            if(leverNode.right!=null) deque.offer(leverNode.right);
        }
        res.add(leverList);
    }
    return res;
}

2 二叉树力扣题解

分治算法应用[1]

思路：先分别处理局部，再合并结果。二叉树的大部分题解思想都用到了分治算法、快排和归并排序也是分治算法的经典应用。

分治法模板：1递归结束条件 2分段处理 3合并结果

public ResultType traversal(ListNode root){
    //1递归结束条件
    if(root==null){
        // do something and return
    }
    //2分治处理
    ResultType left = traversal(root.Left);
    ResultType right = traversal(root.Right);
    //3合并结果
    ResultType result = Merge from left and right；
    return result;
}

遍历都学会了、又学了分治算法的思想，就可以莽力扣题了~

104. 二叉树的最大深度

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

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

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

思路：二叉树的最大深度等于其左子树和右子树最大深度的大值 +1

代码：直接套分治法模板

class Solution {
    public int maxDepth(TreeNode root) {
        //二叉树的最大深度 为左右子树的最大深度+1
        if(root==null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路：平衡二叉树的条件是左右子树都是平衡二叉树且左右子树高差不超过1

代码：先写一个算最大深度的函数，三个判断条件同时满足时为平衡

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        boolean left = isBalanced(root.left);
        boolean right = isBalanced(root.right);
        return left && right&& (Math.abs(maxDepth(root.left)-maxDepth(root.right))<2);
    }
    //写一个计算最大深度的函数
    private int maxDepth(TreeNode root){
        if(root==null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

还可以优化一下maxdepth函数，当不是平衡二叉树的时候返回-1，如果暂且还是平衡才返回最大深度。

class Solution {
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root)==-1? false:true;
    }

    //写一个计算最大深度的函数 判断过程出现不平衡直接返回-1
    private int maxDepth(TreeNode root){
        if(root==null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        if(left==-1||right==-1 || Math.abs(left-right)>1) return -1;
        return Math.max(left,right)+1;
    }
}

101. 对称二叉树

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

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

方法一：自下而上的分治算法解题

思路：要想本节点对称，需要他的左右节点对称。所以要想树的根节点对称，我们可以自底向上的递归判断，只有底层节点对称了、才推出其上一层对称、最后推之根节点对称。直接套用分治法模板：1递归结束条件 2分段处理 3合并结果

递归结束条件
- 当节点左右子节点都为空，则当前节点对称返回true
- 当左右子节点只有一个为空，或者两者都非空但值不等，则返回false
分段处理：如果两节点都非空且值相等，就要继续分段考察这两个子节点的对称情况
- 递归调用判断左子节点的左子节点和右子节点的右子节点是不是对称
- 递归调用判断左子节点的右子节点和右子节点的左子节点是不是对称
合并结果
- 如果递归出来都是真就返回true

代码比较简单

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //分治的思想 本节点对称 需要左右子节点对称
        if(root ==null) return true;
        return helper(root.left, root.right);
    }

    private boolean helper(TreeNode left, TreeNode right){
        //都为空表示父节点是叶子节点 返回真
        if(left==null && right==null) return true;
        //如果只有一个为空 或者都不空但值不相等 返回假
        if(left==null||right==null ||left.val!=right.val) return false;

        // 上面是出口 这里是递归调用
        return helper(left.right,right.left) && helper(left.left , right.right);
    }
}

方法二：自顶而下的迭代方法

思路：和层序遍历的想法一样利用队列来实现二叉树的迭代遍历，不同的是为了验证二叉树的对称属性，每次出队入队两个节点元素。如果出现两个都为空的情况注意continue进入下一次循环直到队列为空。

代码：细节处要注意，运算速度比分治稍慢

class Solution {
    public boolean isSymmetric(TreeNode root) {
    // 方法二 非递归的解决 利用队列 每次同时入队两个出队两个
        if(root==null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            //出队两个
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if(left==null&&right==null) continue;
            if(left==null||right==null||left.val!=right.val) return false;
            //子节点入队 注意顺序
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

112. 路径总和系列

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。叶子节点是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

思路：

分治算法：如果想要root下的某条路径和为target，需要先判断其子节点下是否存在某条路径的和为target-root.val，(向下细分、下层的结果影响上层的结果)

分治算法的三个步骤：1递归结束条件 2分段处理 3合并结果。递归结束条件是已经找到叶子节点、

代码

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //还是分治算法 递归出口就是root为空 或者root为叶子节点
        // 分段处理 就是要判断其左右子节点 是否等满足值等于targetSum-root.val 
        if(root == null) return false; //为空false
        //叶子节点出口
        if(root.left==null&&root.right==null && root.val==targetSum) return true;
        //分段处理
        boolean left = hasPathSum(root.left, targetSum-root.val);
        boolean right = hasPathSum(root.right, targetSum-root.val);
        return left||right; //有一个的和满足就行 
    }
}

113. 路径总和 II

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 target = 22，
       5
      / \
     4   8
    /   / \
   11  13  4
  /  \    / \
 7    2  5   1
返回:
1
2
3
4
[
[5,4,11,2],
[5,8,4,5]
]

思路：回溯算法

与判断是否存在不同，这里需要找到所有和为target的路径。但分治算法的思想仍然是一致的。

递归出口就是已经找到叶子节点或为null
注意list集合的深拷贝

代码：每次选择完之后撤销选择、、

class Solution {
    List<List<Integer>> res;
    List<Integer> cur;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        //简单用回溯的思想看看 两个选择左右子节点
        res = new ArrayList<>();
        cur = new ArrayList<>();
        backtrack(root,targetSum);
        return res;
    }

    private void backtrack(TreeNode root, int target){
        if(root==null) return;
        if(root.left==null&&root.right==null&&root.val==target){
            cur.add(root.val);//做选择
            res.add(new ArrayList<>(cur));
            cur.remove(cur.size()-1);//撤销选择
            return;
        }
        //不是非叶子节点（或叶子节点值不匹配） 做选择
        cur.add(root.val);
        //回溯
        backtrack(root.left,target-root.val);
        backtrack(root.right,target-root.val);
        //撤销选择
        cur.remove(cur.size()-1);
    }
}

437. 路径总和 III

给定一个二叉树的根节点 root ，。

和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

思路:前缀和+dfs回溯

一个节点的前缀和：根节点到达该节点的路径的和
两个节点的路径和（一个几点必须是另一个节点的祖先）：两节点的前缀和之差
将所有节点的前缀和记录在map数组中，键是前缀和的大小，值是同一个前缀和出现的次数（因为有正负数和0，所以可能出现多次）
先用分治递归调用的手段计算出每个节点的前缀和，然后找它的的祖先中有多少前缀和之差等于curSum-target的，有几个res就加几
全局变量：map数组、res、targetSum，局部变量：当前节点的前缀和
dfs函数可以无返回值，每次更新记录res。。计算完当前节点后向左右子节点回溯！！
要注意回溯撤销选择，当map一个子树中的的前缀值用完之后要立马删除，因为要满足“两个节点是同一个子树的条件”

代码：思路挺难的其实

class Solution {
    Map<Integer,Integer> map;
    int res;
    public int pathSum(TreeNode root, int targetSum) {
        //用map存前缀和，和出现的次数（前缀和为根节点到当前节点路径的值）
        //注意回溯从map中删除前缀和，因为要满足“两个节点是同一个子树的条件”
        if(root==null) return 0;
        map = new HashMap<>();
        map.put(0,1); //节点和为0的节点必须有1个
        res = 0;
        getNums(root, targetSum, 0);
        return res;
    }

    private void getNums(TreeNode node, int targetSum, int curSum){
        if(node==null) return;
        curSum += node.val;
        //map中找存在几个 curSum-targetSum 的元素
        res += map.getOrDefault(curSum-targetSum,0);

        //将该curSum加入map中
        map.put(curSum, map.getOrDefault(curSum,0)+1);
        //左右子树递归回溯 计算个数
        getNums(node.left, targetSum, curSum);
        getNums(node.right, targetSum, curSum);
        //将curSum从map中删除
        map.put(curSum, map.getOrDefault(curSum,1)-1);
    }
}

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

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

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

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
 3
 / \
9 20
/
15 7

思路：

仍然是分治的思想： 1递归出口为后序数组已经遍历完成
2分段处理由后序遍历找到根节点由中序遍历找到左右子树的节点个数
- 分段处理中序数组中根节点左边子树部分和右边的子树部分
3合并结果将root指向递归得到的两个子树
要用一个map集合存中序数组，键是node值值是索引方便找左右子树的元素个数

代码

class Solution {
    int[] inorder;
    int[] postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        //要用一个map集合存中序数组，键是node值 值是索引 方便找左右子树的元素个数
        int n = postorder.length;
        if(n==0) return null;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<n;i++){
            map.put(inorder[i],i);
        }
        //递归调用
        return hepler(0,n-1,0,n-1,map);
    }

    private TreeNode hepler(int inoLeft, int inoRight, int postLeft, int postRight, Map<Integer,Integer> map){
        //递归出口
        if(postLeft>postRight) return null;
        if(postLeft == postRight) return new TreeNode(postorder[postRight]);

        //分段处理 由后序遍历找到根节点 由中序遍历找到左右子树的节点个数
        int rootVal = postorder[postRight];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = map.get(rootVal);
        int leftNums = rootIndex-inoLeft;
        int rightNums = inoRight-rootIndex;
        //分别递归获得左右子树
        TreeNode left = hepler(inoLeft,inoLeft+leftNums-1, postLeft, postLeft+leftNums-1, map);
        TreeNode right = hepler(rootIndex+1,inoRight, postRight-1-rightNums+1, postRight-1,map);
        root.left = left;
        root.right =right;
        return root;
    }
}

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

思路：分治思想，注意用map集合保存中序遍历的数组、方便找root的索引和计算左右子树的节点个数

代码：

class Solution {
    int[] preorder;
    int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        //保存中序至map中
        int n = inorder.length;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<n;++i){
            map.put(inorder[i],i);
        }
        //调用递归函数获得树
        return helper(0,n-1,0,n-1,map);
    }

    private TreeNode helper(int preLeft, int preRight, int inoLeft, int inoRight, Map<Integer,Integer> map){
        //递归出口 叶子节点
        if(preLeft>preRight) return null;
        if(preLeft==preRight) return new TreeNode(preorder[preLeft]);

        //由前序遍历找根节点 由中序遍历找左右子树的节点个数
        int rootVal = preorder[preLeft];
        int rootIndex = map.get(rootVal);
        int leftNums = rootIndex-inoLeft;
        int rightNums = inoRight - rootIndex;
        TreeNode root = new TreeNode(rootVal);

        //分段迭代
        TreeNode left = helper(preLeft+1, preLeft+1+leftNums-1, inoLeft, rootIndex-1 , map);
        TreeNode right = helper(preRight-rightNums+1, preRight, rootIndex+1,inoRight, map);
        root.left = left;
        root.right = right;

        return root;
    }
}

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

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

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

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

示例：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，’#’ 标志着每一层的结束。

思路：直接层序遍历，队列中存每一层的元素，遍历时给next指针赋值

代码：

class Solution {
    public Node connect(Node root) {
        //菜鸡我的直白想法其实也是层序遍历
        if(root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int length = queue.size();
            for(int i=0;i<length;++i){
                Node temp = queue.poll();
                //如果不是最后一个元素就指向下一个元素，否则指向空
                if(i==length-1) temp.next=null;
                else temp.next = queue.peek();
                if(temp.left!=null) queue.offer(temp.left);
                if(temp.right!=null) queue.offer(temp.right);
            }
        }
        return root;
    }
}

236. 二叉树的最近公共祖先

示例 1：

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

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

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

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root==p|| root==q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //左右子节点分别是p q
        if(left!=null&&right!=null) return root;
        //p q 都在左子树内 或者都在右子树内
        if(left!=null || right!=null) return left==null? right:left;
        return null; //p q不存在与树中
    }
}

235. 二叉搜索树的最近公共祖先

方法一：递归，比较值的大小

代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root.val<p.val&&root.val<q.val) return lowestCommonAncestor(root.right,p,q);
        if(root.val>p.val&&root.val>q.val) return lowestCommonAncestor(root.left,p,q);
        return root;
        
    }
}

方法二：迭代 while死循环直到root的值在p和q之间

代码：如果p q在同一边继续向那一边往下找，如果位于两边则此时的root就是最近祖先。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = root;
        while(true){
            if(p.val<res.val&&q.val<res.val){
                res=res.left;
            }else if(p.val>res.val&&q.val>res.val){
                res=res.right;
            }else{
                break;
            }
        }
        return res;
    }
}

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

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

示例 1：
1
2
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

方法一：层序遍历迭代的方式

1、将二叉树序列化为字符串，比较容易，直接套用层序遍历过程，并用StringBuilder存结果就好、空节点也要保留，用字符＃代替

2、将字符串反序列化为二叉树：

先将字符串分隔尾字符数组遍历数组
每次遍历出队一个为该节点指定两个子节点并将这两个子节点进队
当所有的元素都进队完毕时表示二叉树已经建立完成

代码：

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        //层序遍历 取出字符存为sb
        if(root==null) return "#";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            if(temp==null) {
                sb.append("#,");
                continue;
            }
            sb.append(temp.val+",");
            //无论是否为空都加入队列
            queue.offer(temp.left);
            queue.offer(temp.right);
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //遍历字符数组，如果不为空，就作为左子节点或者右子节点加到队列中的节点上
        //队列中首先存根节点，然后每次循环，入队两个节点（当前节点的左右子节点）
        if(data=="#") return null;
        String[] arr = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        queue.offer(root);

        for(int i=1;i<arr.length;++i){
            //每次出队一个 入队两个
            TreeNode temp = queue.poll();
            //指定左右子节点
            if(!arr[i].equals("#")){
                TreeNode left = new TreeNode( Integer.parseInt(arr[i]));
                temp.left = left;
                queue.offer(left);//入队第一个
            }
            if(!arr[++i].equals("#")){
                TreeNode right = new TreeNode( Integer.parseInt(arr[i]) );
                temp.right = right;
                queue.offer(right); //入队第二个
            }
        }
        return root;
    }
}

方法二：前序遍历递归实现（更容易实现）

1、序列化也容易，前序遍历

2、反序列化：

将字符串分隔为数组并转换为队列（方便一个一个的按顺序出队列）
递归函数：出口为#表示的空节点，分别处理左子树和右子树，返回根节点

代码

public class Codec {
    // Encodes a tree to a single string.
    StringBuilder sb;
    public String serialize(TreeNode root) {
        //二叉树序列化输出前序遍历的字符串
        sb = new StringBuilder();
        helper01(root);
        return sb.toString();
    }
    private void helper01(TreeNode root){
        if(root==null){
            sb.append("#,");
            return;
        }
        sb.append(root.val+",");
        helper01(root.left);
        helper01(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        List<String> dataList = Arrays.asList(data.split(","));
        Queue<String> queue = new LinkedList(dataList);
        return helper(queue);
        
    }
    private TreeNode helper(Queue<String> queue){
        String nodeVal = queue.poll(); //先出根结点
        if(nodeVal.equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(nodeVal));
        root.left = helper(queue); //再出左子结点
        root.right = helper(queue); //再出右子结点
        return root;
    }
}

3 剑指offer闭眼题

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:
     3
    / \
   4   5
  / \
 1   2
给定的树 B：
1
2
3
4 
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

思路：很巧妙的两层递归

第一层递归找到A中与B树根节点相同的那个结点，用或运算递归调用A树的左右子节点
第二层递归逐个判断B树和A树的一个子结构是否相同直到B树为空

代码：

class Solution {
    public boolean 
        (TreeNode A, TreeNode B) {
        if(A==null||B==null) return false; //空节点不是任何树的子结构
        //第一层递归A树调用子函数 存在即可 找第一个节点
        return isSubTree(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    private boolean isSubTree(TreeNode A, TreeNode B){
        if(B==null) return true; //B先遍历完 表示B是子结构
        if(A==null||A.val!=B.val) return false; //A先为空 或者A B值不等，表示不匹配
        //向下递归A B的子节点
        return isSubTree(A.left,B.left)&&isSubTree(A.right,B.right);
    }
}

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：
   4
  /   \
2 7
/ \ /
1 3 6 9

镜像输出：
    4
   /   \
7 2
/ \ /
9 6 3 1
示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

思路：每个结点的左右子树交换位置即可、怎么操作呢？ 选一种方式遍历二叉树、对每个结点交换其左右结点的位置

代码：

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        //每个结点的左右子树交换位置即可、怎么操作呢
        //选一种方式遍历二叉树、对每个结点 交换其左右结点的位置
        Traversal(root);
        return root;
    }
    void Traversal(TreeNode root){
        if(root == null ) return;
        Traversal(root.left);
        Traversal(root.right);
        //交换当前结点的左右子节点
        TreeNode temp = root.right;
        root.right=root.left;
        root.left=temp;
    }
}

方法二：递归调用返回节点

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        //交换每个节点的左右子节点， 先交换底层叶子节点，然后通过递归向上
        if(root==null) return null;
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。例如: 给定二叉树: [3,9,20,null,null,15,7],
 3
 / \
9 20
/
15 7

返回其层次遍历结果：

[
[3],
[20,9],
[15,7]
]

思路：和层序遍历一样，内部循环保存一层的所有结点。区别是设置一个flag标识，交替从集合头部或尾部进入集合。因为链表适合插入所以这里用LinkedList而不是ArrayList集合。注意每循环一次也就是每处理完一层需要将改变flag的值

代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //拿手菜 唯一的区别是进list时交替 一个逆序一个顺序 用linkedList 加入头加入尾
        List<List<Integer>> res = new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = true;
        while(!queue.isEmpty()){
            int length = queue.size();
            List<Integer> levelList = new LinkedList<>();
            
            for(int i=0;i<length;i++){
                TreeNode tempNode = queue.poll();
                if(flag){
                    levelList.add(tempNode.val);
                }else{
                    levelList.add(0,tempNode.val);
                }
                if(tempNode.left!=null) queue.offer(tempNode.left);
                if(tempNode.right!=null) queue.offer(tempNode.right);
            }
            flag = !flag;
            res.add(levelList);
        }
        return res;
    }
}

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1

3
/
1 4

2
输出: 4

思路：二叉搜索树一般用前序遍历，~~可以直接前序遍历出来数组再找倒数第K个~~。也可以直接逆选取遍历、设置一个计数标识，找到了第k个自动跳出。

计数标识count 和结果res 都需要定义为全局变量方便储存
加一个判断res是否已经改变，可以避免全局遍历，提前跳出中序遍历！！
明明这么简单、我为什么还是做不出来，，

class Solution {
    int k;
    int res = -1;
    int count =0;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        //递归调用
        findK(root);
        return res;

    }
    private void findK(TreeNode root){
        if(res!=-1) return;//提前跳出
        if(root==null) return;
        findK(root.right);
        count++;
        if(count==k) {
            res=root.val;
            return;
        }
        findK(root.left);
    }
}

4 总结

有一说一，当我把递归遍历和层次遍历基本能够默写之后、还是不能做题；又学了自下而上的分治算法（常用且实现简单）和自上而下的迭代算法，这时候做题也不能一次到位，递归的流程的确称得上是千变万化。

递归的代码确实简单，但很多小细节只有总结了记住了才能迅速AC，不然也会很难办。总结如下吧，愿能常看常新：

二叉树的最大深度等于其左子树和右子树最大深度的大值 +1

平衡二叉树的条件是左右子树都是平衡二叉树且左右子树高差不超过1（两层递归）

对称二叉树：只有底层节点对称了、才推出其上一层对称、最后推之根节点对称

递归出口叶子节点或者左右子节点不对称
递归调用检查左右子节点是否对称，左左右右左右右左

路径总和为target：

递归出口：当前节点为空或者找到叶子节点
递归调用左子树是否存在路径或者右子树是否存在路径 target-root.val
如果要存所有路径进集合中，用list集合，思路一样（回溯提高效率）

中序和前序构造二叉树一般右前序找根节点、由中序的map找索引进而得到左右子树的元素个数

递归出口：后序数组已经遍历完成
分段处理由后序遍历找到根节点由中序遍历找到左右子树的节点个数，分别递归获得左右子树

填充每个节点的下一个右侧节点指针：层序遍历是直接给next指针赋值，注意最后一个赋值null

二叉树的最近公共祖先

递归出口：root为空或者当前root为最近祖先
左右分别递归调用。根据返回的结果、判断返回root或者left或者right或者null

二叉树的序列化与反序列化：推荐递归方式

序列化也容易，前序遍历直接拼接返回递归 yyds
反序列化：先将所有元素存入String的队列中，按前序的方法一个一个的取出来。如果为#返回null节点，否则返回有val的节点

树的子结构：很巧妙的两层递归（和平衡树相似）

第一层递归找到A中与B树根节点相同的那个结点，用或运算递归调用A树的左右子节点
第二层递归逐个判断B树和A树的一个子结构是否相同直到B树为空

二叉树的镜像：选一种方式遍历二叉树、对每个结点交换其左右结点的位置

Z字形从上到下打印二叉树：和层序遍历一致，就是进list集合时分别从尾部进、从头部进，所以注意用LinkedList哦

二叉搜索树的第k大节点：建立全局变量的计数标识count 和结果res ，前序遍历模板把输出变成了一个判断，注意count++

All in all, 我是菜鸡。