Day11-2021.1.19-剑指offer十六道二叉树题目的整理。涉及递归，DFS，BFS。

转到2021.1.9-2021.1.31的learning record 首页

2.二叉树

1. 剑指 Offer 07 .重建二叉树
2. 剑指 Offer 26 .树的子结构
3. 剑指 Offer 27 .二叉树的镜像
4. 剑指 Offer 28 .对称的二叉树
5. 剑指 Offer 32 - I 从上到下打印二叉树
6. 剑指 Offer 32 - II 从上到下打印二叉树 II
7. 剑指 Offer 32 - III 从上到下打印二叉树 III
8. 剑指 Offer 33 .二叉搜索树的后序遍历序列
9. 剑指 Offer 34 .二叉树中和为某一值的路径
10. 剑指 Offer 36 .二叉搜索树与双向链表
11. 剑指 Offer 37 .序列化二叉树
12. 剑指 Offer 54 .二叉搜索树的第k大节点
13. 剑指 Offer 55 - I 二叉树的深度
14. 剑指 Offer 55 - II 平衡二叉树
15. 剑指 Offer 68 - I 二叉搜索树的最近公共祖先
16. 剑指 Offer 68 - II 二叉树的最近公共祖先

一些功能函数

1.按照前序遍历去打印树。根→左→右

private static void printTree(TreeNode node) {
    System.out.printf("%d ", node.val);
    if (node.left != null) {
        printTree(node.left);
    }
    if (node.right != null) {
        printTree(node.right);
    }
}

2.对于Arrays.copyOfRange的测试用例。

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        // 对于Arrays.copyOfRange的测试用例
        int[] test = {0, 1, 2, 3, 4, 5, 6};
        int[] array = Arrays.copyOfRange(test, 1, 2);// 只存储了索引为1的元素。
        for (int a : array)
            //array的长度=1a=1
            System.out.println("array的长度=" + array.length + "a=" + a);
    }
}

1.剑指 Offer 07 .重建二叉树 【需要重刷】

前序遍历：根→左→右

中序遍历：左→根→右

后序遍历：左→右→根

思考：还是有点难度的。直接去看评论的讲解还是不容易理解的。推荐直接去看视频讲解：

利用了递归的方法去做的。

前序遍历数组：根→左→右。中序遍历数组：左→根→右

通过遍历中序数组inorder，得到等于preorder[0]（根节点）的索引index，可以将中序遍历数组分开：

中序遍历数组=左子树的中序遍历数组Arrays.copyOfRange(inOrder, 0, index)+根节点

+右子树的中序遍历数组Arrays.copyOfRange(inOrder, index + 1, inOrder.length - 1 + 1))。

通过index，以及中序遍历数组：左→根→右 的规律，那么左子树的长度为index-0=index。

那么前序遍历数组=根节点+左子树的前序遍历数组Arrays.copyOfRange(preOrder, 1, index + 1)

+右子树的前序遍历数组Arrays.copyOfRange(preOrder, index + 1, preOrder.length - 1 + 1)。

import java.util.Arrays;

public class Offer07 {
    public static void main(String[] args) {
        int[] preOrder = {1, 2, 4, 7, 3, 5, 6, 8}; /// 前序遍历
        int[] inOrder = {4, 7, 2, 1, 5, 3, 8, 6}; /// 中序遍历
        TreeNode root = buildTree(preOrder, inOrder);
        printTree(root);
    }

    public static TreeNode buildTree(int[] preOrder, int[] inOrder) {
        // Java中判断一维数组是否为空
        if (preOrder == null || preOrder.length == 0) {
            return null;
        }
        // preOrder 的第一个元素就是根节点。
        TreeNode root = new TreeNode(preOrder[0]);
        int index = findIndex(preOrder, inOrder);
        //root.left=buildTree(左子树的前序数组，左子树的中序数组)
        root.left = buildTree(Arrays.copyOfRange(preOrder, 1, index + 1), Arrays.copyOfRange(inOrder, 0, index));

        //root.right=buildTree(右子树的前序数组，右子树的中序数组)
        root.right = buildTree(Arrays.copyOfRange(preOrder, index + 1, preOrder.length - 1 + 1), Arrays.copyOfRange(inOrder, index + 1, inOrder.length - 1 + 1));

        return root;
    }

    public static int findIndex(int[] preOrder, int[] inOrder) {
        for (int i = 0; i < preOrder.length; i++) {
            if (inOrder[i] == preOrder[0]) {
                return i;
            }
        }
        return 0;
    }

    private static void printTree(TreeNode node) {
        System.out.printf("%d ", node.val);
        if (node.left != null) {
            printTree(node.left);
        }
        if (node.right != null) {
            printTree(node.right);
        }
    }
}

2.剑指 Offer 26 .树的子结构

思考：涉及到递归调用。如果你记住这个题目的做题的思想，那么就容易做出来。具体的思想去看代码吧。

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

空树不是任意一个树的子结构,所以B不为空。非空树不可能是空树的子树，所以A不能为空。

判断B是不是A的子结构:AB完全相等、B是A的左子树的子结构、B是A的右子树的子结构、

AB完全相等:AB头结点值相等，左子树相等，右子树相等。+子树相等=递归调用“AB完全相等”的业务代码

public class Offer26 {
    public static void main(String[] args) {
        TreeNode A = new TreeNode(1);
        A.left = new TreeNode(2);
        A.right = new TreeNode(3);
        printTree(A);
        System.out.println();
        TreeNode B = new TreeNode(1);
        B.left = null;
        B.right = new TreeNode(3);
        printTree(B);
        System.out.println();
        System.out.println(isSubStructure(A, B));
    }

    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        // 输入条件限制
        // 空树不是任意一个树的子结构,所以B不为空。
        // 非空树不可能是空树的子树，所以A不能为空。
        if (A == null || B == null) {
            return false;
        }
        // 判断B是不是A的子结构:AB完全相等、B是A的左子树的子结构、B是A的右子树的子结构、
        return help(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);

        // ✖ 判断B是不是A的子结构:AB完全相等、A的左子树与B完全相等、A的右子树与B完全相等、
        // ✖ return help(A,B)||help(A.left,B)||help(A.right,B); 
    }

    // 验证AB完全相等，那么AB头结点值相等，左子树相等，右子树相等。
    // 判断子树是否相等，需要递归调用"验证AB完全相等"的功能函数。
    private static boolean help(TreeNode A, TreeNode B) {
        // 递归终止条件 只要B为空，A不管为不为空，B都是A的子结构了，即 A中有出现和B相同的结构和节点值。
        if (B == null) {
            return true;
        }
        if (A == null && B != null) {
            return false;
        }
        // 业务代码
        // 验证AB完全相等，那么AB头结点值相等，左子树相等，右子树相等。
        return A.val == B.val && help(A.left, B.left) && help(A.right, B.right);
    }

    private static void printTree(TreeNode node) {
        System.out.printf("%d ", node.val);
        if (node.left != null) {
            printTree(node.left);
        }
        if (node.right != null) {
            printTree(node.right);
        }
    }
}

3.剑指 Offer 27 .二叉树的镜像

思考：涉及递归调用。输入一个二叉树，该函数输出它的镜像。

public class Offer27 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);
        printTree(root);
        System.out.println();
        printTree(mirrorTree(root));
        System.out.println();
    }

    // 二叉树的镜像，也就是左右子树互换。
    public static TreeNode mirrorTree(TreeNode root) {
        // 递归终止条件，
        if (root == null) {
            return null;
        }
        // 这个是c语言中swap交换A，B，两个数据值的模板。
        TreeNode temp = mirrorTree(root.left);
        root.left = mirrorTree(root.right);
        root.right = temp;
        return root;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

4.剑指 Offer 28 .对称的二叉树

思考：涉及到递归调用

public class Offer28 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        printTree(root);
        System.out.println();
        System.out.println(isSymmetric(root));
    }

    // 用来判断一棵二叉树是不是对称的
    public static boolean isSymmetric(TreeNode root) {
        // 空树肯定是镜像对称
        if (root == null) {
            return true;
        }
        // help，业务代码，用于判断左右子树是否对称
        return help(root.left, root.right);
    }

    public static boolean help(TreeNode left, TreeNode right) {
        //递归终止条件
        if (left == null && right == null) {
            return true;
        }
        // 上面已经去除了同时为空的情况，如果两者不同时为空，那么不可能镜像对称，则返回false
        if (left == null || right == null) {
            return false;
        }
        // left.val==right.val && left.left=right.right && left.right=right.left
        return left.val == right.val && help(left.left, right.right) && help(left.right, right.left);
    }


    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

5.剑指 Offer 32 - I 从上到下打印二叉树 【需要重刷】

ArrayList如何转换为int[]数组 https://blog.csdn.net/huanghanqian/article/details/73920439
这个是java8的特性
int[] res = list.stream().mapToInt(Integer::intValue).toArray();

思考：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。这道题是：二叉树的宽度优先搜索

【需要重刷做法2+做法3。做法1是错误的。】

其实这题很明显就是二叉树的宽度优先搜索，

（1）递归调用的一种错误解法

下面贴出一个错误的解法，并思考这么做为什么错了。

这里用到的递归调用的思想是，添加左右子树的值→递归调用左子树（添加左子树的左右子树的值）→递归调用右子树（添加右子树的左右子树的值）

前序遍历输出为：1->2->4->8->9->5->10->11->3->6->12->13->7->14->15

错误解法返回的答案为：[1, 2, 3, 4, 5, 8, 9, 10, 11, 6, 7, 12, 13, 14, 15]。45应该接67，但是没有接，是因为他没有遍历完一层的数据，就进入了下一层，然后再返回来的。

错误来源是：help(root.left, list); // 递归调用左子树（添加左子树的左右子树的值）
help(root.right, list);// 递归调用右子树（添加右子树的左右子树的值）
这样会先遍历完左子树，再去遍历右子树。

修改目标，每次先去遍历完每一层的数据。

import java.util.ArrayList;

// [0,2,4,1,null,3,-1,5,1,null,6,null,8]
public class Offer32_1_1 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        root.left.left.left = new TreeNode(8);
        root.left.left.right = new TreeNode(9);
        root.left.right.left = new TreeNode(10);
        root.left.right.right = new TreeNode(11);
        root.right.left.left = new TreeNode(12);
        root.right.left.right = new TreeNode(13);
        root.right.right.left = new TreeNode(14);
        root.right.right.right = new TreeNode(15);

        printTree(root);
        System.out.println();
        //System.out.println(levelOrder(root));
        //直观性的输出
        System.out.println(levelOrder2(root));
    }

    // 返回数组，那么可以先用链表去存数据，到最后再将链表转为数组
    // 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印
    public static int[] levelOrder(TreeNode root) {
        // 首先，判断输入是否为空
        if (root == null) {
            return new int[0];
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(root.val);
        help(root, list);
        int[] res = list.stream().mapToInt(Integer::intValue).toArray();
        return res;
    }

    public static ArrayList<Integer> levelOrder2(TreeNode root) {
        // 首先，判断输入是否为空
        if (root == null) {
            return new ArrayList<>();
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(root.val);
        help(root, list);
        return list;
    }

    // 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
    // 做法类似于树的前序，中序，后序遍历，只不过之前是打印，现在是向链表里面添加元素
    // 递归调用的思想是，添加左右子树的值→递归调用左子树（添加左子树的左右子树的值）→递归调用右子树（添加右子树的左右子树的值）

    private static void help(TreeNode root, ArrayList<Integer> list) {
        System.out.println(list);
        // 这个是递归调用的终止条件
        if (root == null) {
            return;
        }
        // 节点为空，则自动跳过
        // 添加左右子树的值
        if (root.left != null) {
            list.add(root.left.val);
        }
        if (root.right != null) {
            list.add(root.right.val);
        }
        // 递归调用左子树（添加左子树的左右子树的值）
        help(root.left, list);
        // 递归调用右子树（添加右子树的左右子树的值）
        help(root.right, list);
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val+"->");
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

（2）递归调用【需要重刷】

思考：利用height，起到一个定位的作用。

下面代码的输出结果如下：

1->2->4->8->9->5->10->11->3->6->12->13->7->14->15->
height=0 list=[[]]
height=1 list=[[1], []]
height=2 list=[[1], [2], []]
height=3 list=[[1], [2], [4], []]
height=3 list=[[1], [2], [4], [8]]
height=2 list=[[1], [2], [4], [8, 9]]

height=3 list=[[1], [2], [4, 5], [8, 9]]
height=3 list=[[1], [2], [4, 5], [8, 9, 10]]
height=1 list=[[1], [2], [4, 5], [8, 9, 10, 11]]
height=2 list=[[1], [2, 3], [4, 5], [8, 9, 10, 11]]

height=3 list=[[1], [2, 3], [4, 5, 6], [8, 9, 10, 11]]
height=3 list=[[1], [2, 3], [4, 5, 6], [8, 9, 10, 11, 12]]
height=2 list=[[1], [2, 3], [4, 5, 6], [8, 9, 10, 11, 12, 13]]

height=3 list=[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13]]
height=3 list=[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14]]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

import java.util.ArrayList;
import java.util.List;

// [0,2,4,1,null,3,-1,5,1,null,6,null,8]
public class Offer32_1_2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        root.left.left.left = new TreeNode(8);
        root.left.left.right = new TreeNode(9);
        root.left.right.left = new TreeNode(10);
        root.left.right.right = new TreeNode(11);
        root.right.left.left = new TreeNode(12);
        root.right.left.right = new TreeNode(13);
        root.right.right.left = new TreeNode(14);
        root.right.right.right = new TreeNode(15);

        printTree(root);
        System.out.println();
        // System.out.println(levelOrder(root));
        // 直观性的输出
        System.out.println(levelOrder2(root));
    }

    public static ArrayList<Integer> levelOrder2(TreeNode root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        levelHelper(list, root, 0);
        ArrayList<Integer> tempList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            tempList.addAll(list.get(i));
        }
        return tempList;
    }

    // 返回数组，那么可以先用链表去存数据，到最后再将链表转为数组
    // 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印
    public static int[] levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        levelHelper(list, root, 0);
        // 二维列表转为一维列表
        ArrayList<Integer> tempList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            tempList.addAll(list.get(i));
        }
        //把list转化为数组
//        int[] res = new int[tempList.size()];
//        for (int i = 0; i < tempList.size(); i++) {
//            res[i] = tempList.get(i);
//        }
//        return res;
        int[] res = tempList.stream().mapToInt(Integer::intValue).toArray();
        return res;
    }

    // levelHelper 是主要的业务代码
    public static void levelHelper(ArrayList<ArrayList<Integer>> list, TreeNode root, int height) {
        // 判断输入节点是否为空
        if (root == null) {
            return;
        }
        // >= 中的等于，应该是做初始化的
        if (height >= list.size()) {
            list.add(new ArrayList<>());
        }
        // height起到了一个定位的作用
        System.out.println("height=" + height + " list=" + list);
        list.get(height).add(root.val);
        levelHelper(list, root.left, height + 1);
        levelHelper(list, root.right, height + 1);
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val + "->");
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

（3）二叉树的宽度优先搜索【需要重刷】

思考：二叉树的宽度优先搜索的题解：+建议先看视频讲解：

宽度优先搜索=层序遍历=利用队列queue去做。

思路：从队列queue中取出一个节点，并将其左右节点加入队列queue。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// [0,2,4,1,null,3,-1,5,1,null,6,null,8]
public class Offer32_1_3 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        root.left.left.left = new TreeNode(8);
        root.left.left.right = new TreeNode(9);
        root.left.right.left = new TreeNode(10);
        root.left.right.right = new TreeNode(11);
        root.right.left.left = new TreeNode(12);
        root.right.left.right = new TreeNode(13);
        root.right.right.left = new TreeNode(14);
        root.right.right.right = new TreeNode(15);

        printTree(root);
        System.out.println();
        // System.out.println(levelOrder(root));
        // 直观性的输出
        System.out.println(levelOrder2(root));
    }

    // 返回数组，那么可以先用链表去存数据，到最后再将链表转为数组
    // 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印
    public static int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        int[] res = list.stream().mapToInt(Integer::intValue).toArray();
        return res;
    }

    public static List<Integer> levelOrder2(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return list;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val + "->");
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

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

（1）递归调用

思考：按照递归调用的方法。解法和32 - I 的解法（2）一模一样。

里面的一些小细节要非常注意哈

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// [0,2,4,1,null,3,-1,5,1,null,6,null,8]
public class Offer32_2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        root.left.left.left = new TreeNode(8);
        root.left.left.right = new TreeNode(9);
        root.left.right.left = new TreeNode(10);
        root.left.right.right = new TreeNode(11);
        root.right.left.left = new TreeNode(12);
        root.right.left.right = new TreeNode(13);
        root.right.right.left = new TreeNode(14);
        root.right.right.right = new TreeNode(15);

        printTree(root);
        System.out.println();
        System.out.println(levelOrder(root));
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        help(root, res, 0);
        return res;
    }

    private static void help(TreeNode root, List<List<Integer>> res, int height) {
        if (root == null) {
            return;
        }
        if (height >= res.size()) {
            res.add(new ArrayList<>());
        }
        res.get(height).add(root.val);
        if (root.left != null) {
            help(root.left, res, height + 1);
        }
        if (root.right != null) {
            help(root.right, res, height + 1);
        }
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val + "->");
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

（2）广度优先搜索 从上到下打印二叉树 II 【需要重刷】

你多看几遍这道题，仔细考虑for里面为啥这么写。就能更加深刻的去理解广度优先遍历了。

思想：从队列中取出一个节点，向队列中存入该节点的左右节点。

这里和上面一道题目的区别是，上一题直接返回即可，这道题每一层就需要添加到一个链表里了。

实际输出一下，为什么会出错，将i++换成i--，两种程序的状态是？+下面内容进行解释：

// 易错点：
// 这里的for如果写反了，如果写成i++,那就错了。
for (int i = queue.size(); i > 0; i--)
for (int i = 0; i < queue.size(); i++)
// 应该是这样说，在for循环中，queue.size()的大小随着queue不断的去添加元素，其大小是变化的，所以i < queue.size()的边界是动态的。
// 如果先去用 for (int i = queue.size(); i > 0; i--) ，那么i > 0的边界是确定的，所以不会输出错误的结果。
    
// 更应该思考的是：queue 是存一层的元素，然后 poll 吐出来，存到链表 list 里面。
// 与此同时，去存储树的左右节点到队列 queue 中
// 由于队列的先入先出的特性，所以先去输出上一层的元素，再去输出下一层的元素。

// 正确的答案：
1->2->4->8->9->5->10->11->3->6->12->13->7->14->15->
i = 1 queue.size() = 2 temp = [1]

i = 2 queue.size() = 3 temp = [2]
i = 1 queue.size() = 4 temp = [2, 3]

i = 4 queue.size() = 5 temp = [4]
i = 3 queue.size() = 6 temp = [4, 5]
i = 2 queue.size() = 7 temp = [4, 5, 6]
i = 1 queue.size() = 8 temp = [4, 5, 6, 7]

i = 8 queue.size() = 7 temp = [8]
i = 7 queue.size() = 6 temp = [8, 9]
i = 6 queue.size() = 5 temp = [8, 9, 10]
i = 5 queue.size() = 4 temp = [8, 9, 10, 11]
i = 4 queue.size() = 3 temp = [8, 9, 10, 11, 12]
i = 3 queue.size() = 2 temp = [8, 9, 10, 11, 12, 13]
i = 2 queue.size() = 1 temp = [8, 9, 10, 11, 12, 13, 14]
i = 1 queue.size() = 0 temp = [8, 9, 10, 11, 12, 13, 14, 15]

[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]] 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// [0,2,4,1,null,3,-1,5,1,null,6,null,8]
public class Offer32_2_2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        root.left.left.left = new TreeNode(8);
        root.left.left.right = new TreeNode(9);
        root.left.right.left = new TreeNode(10);
        root.left.right.right = new TreeNode(11);
        root.right.left.left = new TreeNode(12);
        root.right.left.right = new TreeNode(13);
        root.right.right.left = new TreeNode(14);
        root.right.right.right = new TreeNode(15);

        printTree(root);
        System.out.println();
        System.out.println(levelOrder(root));
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            // 每次新建一个 list 去存储每一行的内容
            List<Integer> temp = new ArrayList<>();
            // 这里的for如果写反了，如果写成i++,那就错了。
            for (int i = queue.size(); i > 0; i--) {
//            for (int i = 0; i < queue.size(); i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                System.out.println("i = " + i + " queue.size() = " + queue.size() + " temp = " + temp);
            }
            System.out.println();
            res.add(temp);
        }
        return res;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val + "->");
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

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

（1）递归调用

思考：递归调用，通过高度 height 来控制存储每一层的元素。

没想到合适的做法。明天再想吧。。。主要是这个三份“从上到下打印二叉树”做的脑袋都大了。迷。

（2）广度优先遍历

思考：相对于从上到下打印二叉树 II的变化之处是在向每一层的链表中添加元素，按照奇偶性去选择向链表的首部添加元素，还是向链表的末尾添加元素。

这里借用了LinkedList 双向链表 +双向链表的功能。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// [0,2,4,1,null,3,-1,5,1,null,6,null,8]
public class Offer32_3 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        root.left.left.left = new TreeNode(8);
        root.left.left.right = new TreeNode(9);
        root.left.right.left = new TreeNode(10);
        root.left.right.right = new TreeNode(11);
        root.right.left.left = new TreeNode(12);
        root.right.left.right = new TreeNode(13);
        root.right.right.left = new TreeNode(14);
        root.right.right.right = new TreeNode(15);

        printTree(root);
        System.out.println();
        System.out.println(levelOrder(root));
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            LinkedList<Integer> temp = new LinkedList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (res.size() % 2 == 0) {
                    temp.addLast(node.val);
                } else {
                    temp.addFirst(node.val);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val + "->");
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

8.剑指 Offer 33 .二叉搜索树的后序遍历序列 【需要重刷】

二叉搜索树，它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

您还没任何提交记录。哈哈。竟然没做过这个题目~

思考：单纯去看评论中的讲解是不容易理解的，点击这里去看视频讲解：+视频中应该是有一个错误的点：二叉搜索树，它可能是一棵空树，那么输入数组为空则应该返回true。

使用递归操作去求解问题。只是参考了视频中的解法。评论中大神们的做法还没有去深究。

思想：后序遍历，数组末尾元素为根节点，二叉搜索树：为空树，或者 **左子树所有节点值<根节点值<右子树所有节点值。**这样，根据这个性质，将数组分为左右根，如果不能遍历完全，那肯定是false。如果递归终止条件中list为空，那么说明左子树/右子树遍历完了，返回true，不再执行程序而是结束程序。

import java.util.ArrayList;
import java.util.List;

public class Offer33 {
    public static void main(String[] args) {
//        int[] postorder = new int[]{1, 6, 3, 2, 5};
        int[] postorder = new int[]{1, 3, 2, 6, 5};
        System.out.println(verifyPostorder(postorder));
    }

    public static boolean verifyPostorder(int[] postorder) {
        // 可能是空树
        if (postorder == null || postorder.length == 0) {
            return true;
        }
        // 为了便于操作。作者将数组转为链表
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < postorder.length; i++) {
            list.add(postorder[i]);
        }
        return help(list);
    }

    // 递归遍历
    private static boolean help(List<Integer> list) {
        // 递归终止条件 下面两个条件都可以，都一样。
        // if (list.size() < 1) {
        if (list.size() == 0) {
            return true;
        }
        // 后序遍历：左→右→根。根在数组/链表的末尾
        int rootVal = list.get(list.size() - 1);
        List<Integer> LeftList = new ArrayList<>();
        List<Integer> RightList = new ArrayList<>();
        int i = 0;
        // 为了便于操作。作者将数组转为链表。便利之处在这里，容易进行动态添加元素。
        // 左子树
        while (list.get(i) < rootVal) {
            LeftList.add(list.get(i++));
        }
        // 为了便于操作。作者将数组转为链表。便利之处在这里，容易进行动态添加元素。
        // 右子树
        while (list.get(i) > rootVal) {
            RightList.add(list.get(i++));
        }
        // 这里 i已经执行了加1操作。但是，在正确的二叉搜索树的list里面，左右子树的元素数量和=list.size()-1,又由于list索引从0开始，
        // 所以此时的i的索引为list.size()-1 -1（索引从0开始） +1（i++的操作） =list.size()-1。
        // 如果比这个小，那么不符个规则，返回false。
        if (i < list.size() - 1) {
            return false;
        }
        return help(LeftList) && help(RightList);
    }
}

9.剑指 Offer 34 .二叉树中和为某一值的路径

相同题目：113. 路径总和 II+解析

思考：递归+回溯。一眼看出用回溯，但是忘了怎么写。

回溯法可以看玩转算法的第八章-递归和回溯的做法。实际上做二叉树的题目，递归的做法用到的还是非常多的呢。

回溯法关键在于恢复现场 -> LinkedList类是双向链表，可以用于恢复现场。

题解：

我觉得上面的测试用例是有问题的，‘从树的根节点开始往下一直到叶节点’，如果根节点为空，或者只有根节点，那么即使root.val=sum,这时候也不能去返回只包含根节点的list，因为此时不包括叶子节点。

另外一种说法是：只有一个节点，它是根节点，也是叶子节点。

所以，最终的认定是：根节点也可以被视为叶子节点。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Offer34 {
    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.left.right = null;
        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.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);
        printTree(root);
        System.out.println();
        int sum = 22;
        System.out.println(pathSum(root, sum));
    }

    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {
            return new ArrayList<>();
        }
        LinkedList<Integer> path = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        recur(root, sum, path, res);
        return res;
    }

    private static void recur(TreeNode root, int sum, LinkedList<Integer> path, List<List<Integer>> res) {
        // 递归调用的终止条件 return结束当前程序运行
        if (root == null) {
            return;
        }
        path.add(root.val);
        sum -= root.val;
        // 找到路径：到达叶子节点，并且累计和为sum。
        if (sum == 0 && root.left == null && root.right == null) {
            // 好像是必须这样写，不这样写会报错
            res.add(new ArrayList<>(path));
        }
        // 创建现场
        recur(root.left, sum, path, res);
        recur(root.right, sum, path, res);
        // 恢复现场，去掉最后加入的结点
        path.removeLast();
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

※先跳过※10.剑指 Offer 36 .二叉搜索树与双向链表

您还没任何提交记录。哈哈。竟然没做过这个题目~

注意：本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/ vip专享

思考：看题目，还是涉及到了二叉搜索树，左<根<右。按照中序遍历的方法，可以得到一个递增的序列。

这道题目，在IDEA中也不好设置测试用例。双向链表的话，貌似是一个环，没有边界。没考虑测试的细节

新建一个Node类。这个题目要求返回的也是Node类。感觉和TreeNode类没有差别。

public class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

代码：来源b站的视频讲解，但是力扣还是没有通过，尴尬。：

import java.util.ArrayList;
import java.util.List;

public class Offer36_1 {
    public static void main(String[] args) {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        printTree(root);
        System.out.println();
        System.out.println(treeToDoublyList(root));
    }

    private static Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        List<Node> list = new ArrayList<>();
        // 中序遍历二叉搜索树，可以获得一个递增的链表list。
        InOrder(root, list);
//        for (int i = 0; i < list.size(); i++) {
//            System.out.print(list.get(i).val + "->");
//        }
//        System.out.println();
        // 一个递增的链表list的首部元素作为head
        Node head = list.get(0);
        Node ptr = head;
        head.left = null;
        for (int i = 1; i < list.size(); i++) {
            ptr.right = list.get(i);
            list.get(i).left = ptr;
            // 更新节点
            ptr = ptr.right;
        }
        // 返回要求的双向链表
        return head;
    }

    private static void InOrder(Node root, List<Node> list) {
        if (root == null) {
            return;
        }
        InOrder(root.left, list);
        list.add(root);
        InOrder(root.right, list);
    }

    private static void printTree(Node root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

可以通过的代码 题解链接：+可能也不太好理解吧。

class Solution {
    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        dfs(root);

        pre.right = head;
        head.left =pre;//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的

        return head;

    }

    public void dfs(Node cur){
        if(cur==null) return;
        dfs(cur.left);

        //pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点
        if(pre==null) head = cur;
        //反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
        else pre.right = cur;
       
        cur.left = pre;//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。

        pre = cur;//pre指向当前的cur
        dfs(cur.right);//全部迭代完成后，pre指向双向链表中的尾节点
    }
}

作者：jyd

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

※11.剑指 Offer 37 .序列化二叉树

您还没任何提交记录。哈哈。竟然没做过这个题目~困难程度的类型。

本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

思考：自己做的序列化，还有点问题，在于多输出了null。我看他们的输出也为：1,2,3,null,null,4,5,null,null,null,null，那我的没有错误吧。

（1）BFS 解法

序列化——很典型的 BFS
维护一个队列，初始让根节点入列，考察出列节点：
如果出列的节点是 null，将符号 ‘X’ 推入 res 数组。
如果出列的节点不是 null，将节点值推入数组 res，并将它的左右子节点入列。
注意，子节点 null 也入列，它对应 “X”，需要被记录，只是它没有子节点可入列。
入列、出列…直到队列为空，所有节点遍历完，res 也好了，转成字符串就是结果。

作者：xiao_ben_zhu
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/shou-hui-tu-jie-gei-chu-dfshe-bfsliang-chong-jie-f/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("X,");
            } else {
                sb.append(node.val + ",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "") {
            return null;
        }
        Queue<String> nodes = new ArrayDeque<>(Arrays.asList(data.split(",")));
        TreeNode root = new TreeNode(Integer.parseInt(nodes.poll()));
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            String left = nodes.poll();
            String right = nodes.poll();
            if (!left.equals("X")) {
                node.left = new TreeNode(Integer.parseInt(left));
                queue.add(node.left);
            }
            if (!right.equals("X")) {
                node.right = new TreeNode(Integer.parseInt(right));
                queue.add(node.right);
            }
        }
        return root;
    }
}

DFS：

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "X,";
        }
        String left = serialize(root.left);
        String right = serialize(root.right);
        return root.val + "," + left + right;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        Queue<String> queue = new ArrayDeque<>(Arrays.asList(nodes));
        return buildTree(queue);
    }

    public TreeNode buildTree(Queue<String> queue) {
        String value = queue.poll();
        if (value.equals("X")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = buildTree(queue);
        node.right = buildTree(queue);
        return node;
    }
}

（1）序列化

public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) return "X,";
            String leftSerialize = serialize(root.left); //左子树的序列化字符串
            String rightSerialize = serialize(root.right); //右子树的序列化字符串
            return root.val + "," + leftSerialize + rightSerialize;
        }

        // Decodes your encoded data to tree.
        /**
         * 构建树的函数 buildTree 接收的 “状态” 是 list 数组，由序列化字符串转成
         * 按照前序遍历的顺序：先构建根节点，再构建左子树、右子树
         * 将 list 数组的首项弹出，它是当前子树的 root 节点
         * 如果它为 'X' ，返回 null
         * 如果它不为 'X'，则为它创建节点，并递归调用 buildTree 构建左右子树，当前子树构建完毕，向上返回
         */
        public TreeNode deserialize(String data) {
            String[] temp = data.split(",");
            Deque<String> dp = new LinkedList<>(Arrays.asList(temp));
            return buildTree(dp);
        }
        private TreeNode buildTree(Deque<String> dq){
            String s = dq.poll(); //返回当前结点
            if (s.equals("X")) return null;
            TreeNode node = new TreeNode(Integer.parseInt(s));
            node.left = buildTree(dq); //构建左子树
            node.right = buildTree(dq); //构建右子树
            return node;
        }
    }

（2）反序列化

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

类型：简单

思考：可以这样考虑，先按照左根右的顺序遍历树，并将值存储到链表list中，这样得到的是递增的序列，向链表中添加元素时，需要addFirst：在列表首部添加元素，而不是List.add() 或 addLast 方法用于在列表的尾部插入指定元素。然后得到k即可。

List.add() 方法用于在列表的尾部插入指定元素。

addFirst：在列表首部添加元素
addLast：在列表末尾添加元素

当然了，可以右根左的顺序，这样就可以得到递减序列的吗？？？存在疑问，先试试。没问题，哈哈！

但是呢，这种做法的性能差了好多。

import java.util.LinkedList;

public class Offer54 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        printTree(root);
        System.out.println();
        int k = 1;
        System.out.println(kthLargest(root, k));
    }

    public static int kthLargest(TreeNode root, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        help(root, list);
        // 第一大的数的索引在0的位置。
        return list.get(k - 1);
    }

    private static void help(TreeNode root, LinkedList<Integer> list) {
        if (root == null) {
            return;
        }
        help(root.right, list);
//        list.addFirst(root.val);
        list.add(root.val);
        help(root.left, list);
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

13.剑指 Offer 55 - I 二叉树的深度

（1）DFS

思考：简单题型。深度优先遍历。从顶层去考虑，就是根节点的深度1 + 左右子树的最大深度。递归终止条件。

public class Offer55_1_DFS {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        printTree(root);
        System.out.println();
        System.out.println(maxDepth(root));
    }

    // 深度优先遍历。从顶层去考虑，就是根节点的深度1 + 左右子树的最大深度。递归终止条件。
    public static int maxDepth(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

（2）BFS

广度优先遍历。重点在于维护队列，队列添加的是node节点值，而不是数值，因为在这里还需要 queue.add(node.left);，queue.add(node.right);。

import java.util.LinkedList;
import java.util.Queue;

public class Offer55_1_BFS {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        printTree(root);
        System.out.println();
        System.out.println(maxDepth(root));
    }

    // 广度优先遍历。重点在于维护队列
    public static int maxDepth(TreeNode root) {
        // 输入判断条件
        if (root == null) {
            return 0;
        }
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            res++;
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return res;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

14.剑指 Offer 55 - II 平衡二叉树

（1）DFS，自上向下

思考：简单题型。一眼就看出这是一道深度优先遍历。这个按照定义去写业务代码即可。

平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

现在自己做的性能差一些，如果自己考虑到自顶向上+记忆化搜索，或者自底向上，性能也可以提高。

public class Offer55_2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.left.left = null;
        root.left.right = null;
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        printTree(root);
        System.out.println();
        System.out.println(isBalanced(root));
    }

    // 平衡二叉树定义(AVL)：它或者是一颗空树，
    // 或者具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        // (Math.abs(MathDepth(root.left) - MathDepth(root.right)) <= 1) 系统给简化了，我自己写的时候用的是三目元算符 （?:）
        return (Math.abs(MathDepth(root.left) - MathDepth(root.right)) <= 1) && isBalanced(root.left) && isBalanced(root.right);
    }

    private static int MathDepth(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return 0;
        }
        return Math.max(MathDepth(root.left), MathDepth(root.right)) + 1;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

（2）DFS，自底向上

public class Offer55_3 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.left.left = null;
        root.left.right = null;
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        printTree(root);
        System.out.println();
        System.out.println(isBalanced(root));
    }

    // 平衡二叉树定义(AVL)：它或者是一颗空树，
    // 或者具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
    public static boolean isBalanced(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return true;
        }
        if (!isBalanced(root.left)) {
            return false;
        }
        if (!isBalanced(root.right)) {
            return false;
        }
        return Math.abs(MathDepth(root.left) - MathDepth(root.right)) <= 1;
    }

    private static int MathDepth(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return 0;
        }
        return Math.max(MathDepth(root.left), MathDepth(root.right)) + 1;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

（3）另外的一种解法：

并不容易理解哈~，如果自己考虑到自顶向上+记忆化搜索，或者自底向上，性能也可以提高。

这个题解虽然好一点吧，但是费脑子，算了，先不记了。。。。。。

public class Solution55_2 {

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

    //用left，right记录root左右子节点的深度，避免遍历root时对左右节点的深度进行重复计算。
    //考虑到需要同时记录各个节点的深度和其是否符合平衡性要求，这里的返回值设为int,用一个特殊值-1来表示出现不平衡的节点的情况，而不是一般采用的boolean
    public int dfs(TreeNode root){
    	//用后序遍历的方式遍历二叉树的每个节点（从底至顶）,先左子树，再右子树，最后根节点，
        if(root==null) return 0;//root等于0时，该节点符合要求，返回其深度0，而不返回-1；
        int left = dfs(root.left);//left最开始的取值为0，从底朝上遍历，先左子树，后右子树，最后根节点
        if(left==-1) return -1;//若出现节点的深度为-1，则进行剪枝，开始向上返回，之后的迭代不再进行
        int right = dfs(root.right);
        if(right==-1) return -1;
        return Math.abs(right-left)<2?Math.max(left,right)+1:-1;//+1不能少
        //最开始计算的是左子树最左侧的一个叶节点，其左右子节点不存在，left=0，right=0，满足条件，返回该叶节点的深度max(0,0)+1=1;
    }
}

15.剑指 Offer 68 - I 二叉搜索树的最近公共祖先

思考：简单类型，主要利用二叉搜索树的性质，左子树所有节点<根节点<右子树所有节点

（1）递归调用

// 这里是业务代码，细节的地方千万不要写错。
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
}

public class Offer68_1 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        TreeNode p = new TreeNode(2);
        TreeNode q = new TreeNode(8);
        printTree(root);
        System.out.println();
        TreeNode resNode = lowestCommonAncestor(root, p, q);
        System.out.println(resNode.val);
    }

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

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

（2）迭代

题解：

// 业务代码
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        } else {
            break;
        }
    }
    return root;
}

public class Offer68_1_method2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        TreeNode p = new TreeNode(2);
        TreeNode q = new TreeNode(8);
        printTree(root);
        System.out.println();
        TreeNode resNode = lowestCommonAncestor(root, p, q);
        System.out.println(resNode.val);
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                break;
            }
        }
        return root;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

16.剑指 Offer 68 - II 二叉树的最近公共祖先

1.首先求出两节点到根节点的路径。

2.求出两条路径中最后一个相同的节点。

您还没任何提交记录。二叉树里的最强王者 不容错过的笔试必考题 。

三种解法：

小美图解视频讲解：评论，代码短，但是难度高：

视频讲解

视频讲解-动画版本✔

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BOkDtRVo-1611062710430)(…/AppData/Roaming/Typora/typora-user-images/image-20210119204643310.png)]

思考：虽然官方标注的是简单的类型，但是其实并不简单。题解：

本题与主站 236 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

由于涉及到双端链表的操作，这里做一下测试

import java.util.LinkedList;

public class Offer {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        // [1, 2, 3, 4]
        System.out.println(list);
        // list.peek()=1
        System.out.println("list.peek()=" + list.peek());//顶端
        // list.peekFirst()=1
        System.out.println("list.peekFirst()=" + list.peekFirst());//顶端
        // list.peekLast()=4
        System.out.println("list.peekLast()=" + list.peekLast());//末尾.
        // [1, 2, 3, 4]
        System.out.println(list);
        // list.pollFirst()=1  list=[2, 3, 4]
        System.out.println("list.pollFirst()=" + list.pollFirst() + "  list=" + list);
    }
}

（1）递归调用，这个的业务代码还挺短的，自己好好理解一下

如果是单纯的通过这一道题目，业务代码少，容易记忆。

对于 lowestCommonAncestor 这个函数的理解的话，它不一定可以返回最近的共同祖先，如果子树中只能找到 p 节点或者 q 节点，它最终返回其实就是 p 节点或者 q 节点。这其实对应于最后一种情况，也就是 leftCommonAncestor 和 rightCommonAncestor 都不为 null，说明 p 节点和 q 节点分处于两个子树中，直接 return root。

在左子树中没有找到，那一定在右子树中
在右子树中没有找到，那一定在左子树中

对于这句话，我是存在疑惑的，这样会不会导致错误呢？

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 递归终止条件
    if (root == null || root == p || root == q) {
        return root;
    }
    // 调用自身。调用 lowestCommonAncestor
    TreeNode leftCommonAncestor = lowestCommonAncestor(root.left, p, q);
    TreeNode rightCommonAncestor = lowestCommonAncestor(root.right, p, q);
    //在左子树中没有找到，那一定在右子树中
    if (leftCommonAncestor == null) {
        return rightCommonAncestor;
    }
    //在右子树中没有找到，那一定在左子树中
    if (rightCommonAncestor == null) {
        return leftCommonAncestor;
    }
    //不在左子树，也不在右子树，那说明是根节点
    return root;
}

完整代码

import java.util.Stack;

public class Offer68_2_2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(7);
        printTree(root);
        System.out.println();
        TreeNode resNode = lowestCommonAncestor(root, p, q);
//        System.out.println(resNode.val);
    }

    // 对于 lowestCommonAncestor 这个函数的理解的话，它不一定可以返回最近的共同祖先，
    // 如果子树中只能找到 p 节点或者 q 节点，它最终返回其实就是 p 节点或者 q 节点。
    // 这其实对应于最后一种情况，也就是 leftCommonAncestor 和 rightCommonAncestor 都不为 null，
    // 说明 p 节点和 q 节点分处于两个子树中，直接 return root。

    // 是因为自己没有深刻的理解哈。
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件：到达叶子结点后的空节点，或者查找到题目中给出的节点p或者节点q
        if (root == null || root == p || root == q) {
            return root;
        }
        // 调用自身。调用 lowestCommonAncestor
        // 在左子树中查找两个指定节点的最近公共祖先。
        TreeNode leftCommonAncestor = lowestCommonAncestor(root.left, p, q);
        // 在右子树中查找两个指定节点的最近公共祖先。
        TreeNode rightCommonAncestor = lowestCommonAncestor(root.right, p, q);
//        这句话是错误的。
//        if (leftCommonAncestor == null && rightCommonAncestor == null) {
//            return root;
//        }
        //在左子树中没有找到，那一定在右子树中
        if (leftCommonAncestor == null) {
            return rightCommonAncestor;
        }
        //在右子树中没有找到，那一定在左子树中
        if (rightCommonAncestor == null) {
            return leftCommonAncestor;
        }
        //不在左子树，也不在右子树，那说明是根节点
        return root;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

（2） 这一个思路还是容易懂的，但是报错了，自己修改下吧。但是系统可以通过，IDEA不能通过。性能也差。

// 这一个思路还是容易懂的，但是报错了，自己修改下吧。但是系统可以通过，IDEA不能通过。
import java.util.Stack;

public class Offer68_2_1 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(7);
        printTree(root);
        System.out.println();
        TreeNode resNode = lowestCommonAncestor(root, p, q);
        System.out.println(resNode.val);
    }

    // 这道题的话我们只有通过遍历去寻找给定的节点，从而确定节点是在左子树还是右子树了。
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q) {
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
        //中序遍历判断两个节点是否在左子树
        TreeNode cur = root.left;
        boolean pLeft = false;
        boolean qLeft = false;
        while (cur != null || !stack.isEmpty()) {
            // 节点不为空一直压栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left; // 考虑左子树
            }
            // 节点为空，就出栈
            cur = stack.pop();
            // 判断是否等于 p 节点
            if (cur == p) {
                pLeft = true;
            }
            // 判断是否等于 q 节点
            if (cur == q) {
                qLeft = true;
            }

            if (pLeft && qLeft) {
                break;
            }
            // 考虑右子树
            cur = cur.right;
        }

        //两个节点都在左子树
        if (pLeft && qLeft) {
            return lowestCommonAncestor(root.left, p, q);
            //两个节点都在右子树
        } else if (!pLeft && !qLeft) {
            return lowestCommonAncestor(root.right, p, q);
        }
        //一左一右
        return root;
    }

    private static void printTree(TreeNode root) {
        System.out.print(root.val);
        if (root.left != null) {
            printTree(root.left);
        }
        if (root.right != null) {
            printTree(root.right);
        }
    }
}

最后

以上就是虚幻钢铁侠为你收集整理的Day11-2021.1.19-剑指offer十六道二叉树题目的整理。涉及递归，DFS，BFS。的全部内容，希望文章能够帮你解决Day11-2021.1.19-剑指offer十六道二叉树题目的整理。涉及递归，DFS，BFS。所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。