【数据结构】(8) 二叉树

一、树形结构

1、什么是树形结构

• 根节点没有前驱，其它节点只有一个前驱（双亲/父结点）。
• 所有节点可以有 0 ~ 多个后继，即分支（孩子结点）。
• 每个结点作为子树的根节点，这些子树互不相交。

2、关于树概念词

节点的度：节点的分支数。

树的度：树中最大的结点的度。

节点的层次：根为第一层。

树的高度：最大层次。

兄弟结点：同父的结点：

堂兄弟结点：同爷爷的结点。

节点的祖先：从根到该结点路径上的所有结点。

子孙：某节点为根，其子树中任意结点。

森林：互不相交的树集合。

3、树的表示形式

        很多种，简单了解最常用（这种表示法，方便将树转为二叉树）的孩子兄弟表示法：

class Node {
    int data; // 存数据
    Node firstChild; // 存第一个孩子
    Node firstBrother; // 存第一个兄弟
}

二、二叉树

1、什么是二叉树

• 树的度为2。
• 子树有左右之分，不能颠倒。

2、特殊的二叉树

• 满二叉树：若k表示结点层数，则每层结点数都等于 2^(k-1) 的树就是满二叉树。
• 完全二叉树：每个结点编号与满二叉树中每个节点编号一一对应的树。

3、二叉树性质

3.1、性质

• 第 k 层最多有 2^(k-1) 个结点。
• 高度为 k 的二叉树最多有 (2^k) - 1 个结点。
• 任意二叉树，叶子节点个数 n0 和有两个度的结点个数 n2 有关系：n0 = n2+1。

推导：n = n0+n1+n2 个结点，除了根节点都有前驱，故一共 n-1 个度。n-1 = 0*n0+1*n1+2*n2。

联合两个式子得到：n0 = n2 + 1。

• n 个节点的完全二叉树深度为 log(n+1) 上取整。

推导：n = (2^k)-1，k = log(n+1)。完全二叉树结点数肯定小于等于满二叉树结点数，所以 n 可能不够，结果就上取整。

• 从根节点开始（编号0），从左往右给每个结点编号：

① 双亲编号： i=0，根节点，无双亲；i>0，双亲编号=(i-1)/2。

② 左孩子编号：若 2*i+1 < n，左孩子编号  2*i+1；否则没左孩子。

③ 右孩子编号：若 2*i+2 < n，右孩子编号  2*i+2；否则没右孩子。

3.2、练习题

4、二叉树的遍历

4.1、遍历方式

前序：根>>左>>右，ABDCEF。

中序：左>>根>>右，DBAECF。

后序：左>>右>>根，DBEFCA。

层序：从上到下，从左往右，ABCDEF。

4.2、遍历序列转二叉树

        如果想根据遍历序列获得二叉树，则必须是两种遍历序列，并且其中一种必须是中序遍历。因为，前、后、层序遍历序列能得知每个子二叉树的根；中序遍历能得知某根的左右子树。

4.3、代码（递归）

        二叉树的存储结构有顺序存储和链式存储，本文只讨论了链式存储。

        二叉树的表示形式：

public class BinaryTree {
    public static class TreeNode {
        char value;
        TreeNode left;
        TreeNode right;

        public TreeNode(char value) {
            this.value = value;
        }
    }

    private TreeNode root;

    ............
}

        构造一棵二叉树（主要为了测试，这种构造方式不可取）：

    public void createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');

        A.left = B;
        A.right = C;
        B.left = D;
        C.left = E;
        C.right = F;

        root = A;
    }

        前序遍历：

    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

        中序遍历：

    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.value + " ");
        inOrder(root.right);
    }

        后序遍历：

    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value + " ");
    }

4.4、代码（非递归）：

        前序遍历：144. 二叉树的前序遍历 - 力扣（LeetCode）

        分析：深度优先遍历，左子树遍历完后，转到右子树，需要获得父亲结点，属于后进先出，用栈实现。

        对于非空树：当前处理子树的根 cur 的初始值为 root。

        step1：树不为空，树根 cur 入栈，并打印。若左子树不为空，更新子树 cur 为左子树，重复step1。直到遇到左子树为空，即 cur 为空停止上述循环。转到step2，开始判断右子树。

        step2：弹出栈顶元素，即左子树的父结点，用于转到右子树，若右子树为空，重复step2。直到栈为空，且右子树仍为空时，树遍历完成；或者遇到右子树不为空，更新子树 cur 为右子树，重复 step1，开始遍历右子树。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>(); // 栈，用于左子树遍历完后，获取父节点，转到遍历右子树
        List<Integer> list = new ArrayList<>(); // 打印序列
        // 空树，不打印
        if(root == null) {
            return list;
        }
        TreeNode cur = root; // 当前处理子树的根。对于非空树，初始值为 root。

        // 栈不为空，说明还有右子树需要判断
        // cur不为空，说明还有非空右子树需要遍历
        while(!stack.isEmpty() || cur != null) { 
            // step1
            // 一直是 push 操作，不需要判断栈空
            // 处理情况1：直到左子树为空，退出循环，再转到 step2
            // 处理情况2：右子树不为空，需要遍历右子树，转到 step1
            while(cur != null) {
                stack.push(cur); // 当前处理子树的根节点入栈
                list.add(cur.val); // 打印当前处理子树的根结点
                cur = cur.left; // 转到左子树
            }
            // step2
            cur = stack.pop(); // 弹出栈顶元素
            cur = cur.right; // 转到右子树
        }
        return list;
    }
}

        中序遍历：94. 二叉树的中序遍历 - 力扣（LeetCode）

        分析：左根右，根保存在栈中。先遍历左子树，左子树遍历完后，弹出根时打印根，最后遍历右子树。依然是用栈保存父节点，用于转向右子树。

        方法与前序遍历类似，只不过打印根的位置不同。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>(); 
        if(root == null) {
            return list;
        }
        TreeNode cur = root; 

        while(!stack.isEmpty() || cur != null) { 
            while(cur != null) {
                stack.push(cur); 
                cur = cur.left; 
            }
            cur = stack.pop(); 
            list.add(cur.val); // 弹出父节点（根结点）时，才打印根
            cur = cur.right; 
        }
        return list;
    }
}

        后续遍历：145. 二叉树的后序遍历 - 力扣（LeetCode）

        分析：左右根，左子树遍历完后，父节点不能弹出栈，右子树遍历完后，父节点再弹出栈打印。

        我们现在需要思考，右子树遍历完的标志是什么。比如上图这棵树，在遍历到 F 时，栈中元素应该为：A, C, F。当前父节点 F 的左子树为 null 不遍历，右子树也为 null 不遍历，弹出根 F 并打印，此时栈为：A，C。当前父节点 C 的右子树是F，F已遍历完，需要弹出根C并打印......

        可以观察到，当前父节点（栈顶元素）的右子树为空，或者父节点的右孩子是上一次弹出的栈顶元素时， 表示右子树遍历结束。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>(); 
        if(root == null) {
            return list;
        }
        TreeNode cur = root; 
        TreeNode pre = null; // 存储上一次遍历完成的子树的根
        while(!stack.isEmpty() || cur != null) { 
            while(cur != null) {
                stack.push(cur); 
                cur = cur.left; 
            }
            TreeNode top = stack.peek(); // 查看父节点元素，继续判断是否要遍历右子树
            // 父节点的右孩子为空，或者父节点的右孩子是上一次遍历完的子树（上一次弹出的根），则表示其右子树遍历完成
            // cur 不能改变，仍为 null，表示右子树已经遍历完了，不需要再在step1中遍历。所以用 top 暂存父节点
            if(top.right == null || top.right == pre) {
                stack.pop(); // 弹出父节点
                list.add(top.val); // 打印父节点
                pre = top; // 保存遍历完的子树的根
            } else { // 右子树没遍历完，继续遍历父节点的右子树
                cur = top.right; 
            }
        }
        return list;
    }
}

        层序遍历：使用队列，根节点开始，从上往下，从左到右，先进先出。每弹出一个结点，打印该节点，让后将其孩子全部依次入队。直到队列为空结束。

    public void levelOrder() {
        Queue<TreeNode> queue = new LinkedList<>(); // 队列
        if (root == null) { // 空树
            return;
        }
        queue.offer(root); // 根节点入队
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); // 出队
            System.out.print(node.value + " "); // 打印
            if (node.left!= null) { // 左孩子不为空，入队
                queue.offer(node.left);
            }
            if (node.right!= null) { // 右孩子不为空，入队
                queue.offer(node.right);
            }
        }
    }

5、二叉树的基本操作

5.1、求树中节点个数

        遍历思想：把遍历中的打印结点，换为计数结点。

    private int count; 

    public int size() {
        count = 0;
        size(root);
        return count;
    }

    public void size(TreeNode root) {
        if (root == null) {
            return;
        }
        count++;
        size(root.left);
        size(root.right);
    }

        子问题思想：树的结点树=左数结点数+右数结点数+1。

    public static int size2(TreeNode root) {
        if (root == null) { // 空树，0个结点
            return 0;
        }
        return size2(root.left) + size2(root.right) + 1;
    }

5.2、求叶子节点个数

        遍历思想：把打印结点换为，是叶子结点就计数。

    private int leafCount;
    public int leafCount() {
        leafCount = 0;
        leafCount(root);
        return leafCount;
    }
    
    public void leafCount(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafCount++;
        }    
        leafCount(root.left);
        leafCount(root.right);
    }

        子问题思想：树的叶子结点个数=左子树叶子节点个数+右子树叶子节点个数。

    public static int leafCount2(TreeNode root) {
        if (root == null) { // 空树，0个叶子节点
            return 0;
        }
        if (root.left == null && root.right == null) { // 只有一个根结点，1个叶子节点
            return 1;
        }
        return leafCount2(root.left) + leafCount2(root.right);
    }

5.3、求第K层结点个数

        遍历思想：把打印结点换成，是第 K 层结点就计数。（遍历整棵树。）

    private int levelCount;
    public int levelCount(int k) {
        levelCount = 0;
        levelCount(root, k);
        return levelCount;
    }

    public void levelCount(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        if (k == 1) {
            levelCount++;
        }
        levelCount(root.left, k - 1);
        levelCount(root.right, k - 1);
    }

        子问题思想：树的第K层结点个数=左子树的第K-1层节点个数+右子树的第K-1层节点个数。（如果K合法，到第K层为止，效率比遍历思想更高。）

    public static int levelCount2(TreeNode root, int k) {
        if (root == null) { // 空树，没有节点
            return 0;
        }
        if (k == 1) { // 树的第一层结点为根，1个节点
            return 1;
        }
        return levelCount2(root.left, k - 1) + levelCount2(root.right, k - 1);
    }

5.3、求二叉树的高度

        子问题思想：树的高度=max(左子树高度，右子树高度)+1。

        时间复杂度=调用递归函数的次数=O(n)。

        空间复杂度，因为调用到叶子节点后，就会释放空间，再遍历另一个分叉，因此空间复杂度是树的高度=O(logN)。

    public static int height(TreeNode root) {
        if (root == null) { // 空树，深度为0
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }

5.4、检测 value 是否在树中

        子问题思想：是根，返回根节点地址；搜索左子树，返回值不为空，返回地址；搜索右子树，返回值不为空，返回地址；否者，返回 nll。

        最坏时间复杂度：O(N)

    public static TreeNode findValue(TreeNode root, char value) {
        if (root == null) { // 树为空，没有结点
            return null;   
        }
        if (root.value == value) { // 是根节点
            return root;
        }
        TreeNode left = findValue(root.left, value); // 搜索左子树
        if (left!= null) { // 找到了
            return left;
        }
        return findValue(root.right, value); // 搜索右子树
    }

5.5、判断树是否为完全二叉树

        思路：空树必为完全二叉树。层序遍历树，空结点要入队。遇到第一个空结点，如果是完全二叉树，则在队列中，这个空结点的右边必全是空结点；如果不是完全二叉树，在队列中，其右必存在不为空结点。

        故遇到空结点后，马上在队列中判断其后是否都为空，是则为完全二叉树；否则不为。

    public static boolean isComplete(TreeNode root) {
        if(root == null) { // 空树
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>(); // 队列
        queue.offer(root); // 根节点入队
        while (!queue.isEmpty()) { // 层序遍历树，寻找树中第一个空结点
            TreeNode node = queue.poll(); // 弹出一个结点
            if (node != null) {
                queue.offer(node.left); // 左孩子入队
                queue.offer(node.right); // 右孩子入队
            } else { // 遇到空结点，退出循环
                break;
            }
        }
        // 判断空结点后是否都为空姐点
        while (!queue.isEmpty()) {
            if (queue.poll() != null) { // 还有非空结点，不是完全二叉树
                return false;
            }
        }
        return true;
    }

6、二叉树相关OJ题

6.1、分层包装

102. 二叉树的层序遍历 - 力扣（LeetCode）

分析：在正常前序遍历的基础上，根节点入队，得到初始队列。>> 依次出队，包装为一层，添加到树中。其孩子依次入队，作为下一层。>> 重复上述操作，直到下一层为空。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) { // 空树
            return list;
        }
        // 初始，根节点入队
        Queue<TreeNode> queue = new LinkedList<>(); // 下一层队列
        queue.offer(root); 

        while(!queue.isEmpty()) { // 直到下一层为空
            List<Integer> curLevel = new ArrayList<>(); // 当前层 
            int size = queue.size(); // 处理下一层，下一层作为当前层的大小
            while(size-- != 0) { // 遍历队列，包装为层，将每个结点的孩子放入下一层
                TreeNode node = queue.poll(); // 弹出一个结点
                curLevel.add(node.val); // 包装到当前层中
                if(node.left != null) { // 左孩子放入下一层
                    queue.offer(node.left);
                }
                if(node.right != null) { // 右孩子放入下一层
                    queue.offer(node.right);
                }
            }
            list.add(curLevel);
        }
        return list;
    }
}

6.2、两颗相同的树

100. 相同的树 - 力扣（LeetCode）

分析：子问题思想。两根为空，必相同。一根为空，一根不为空，必不相同。两根不为空，两值不同，必不相同；两值相同，两棵树的左子树相同且右子树相同，则相同，否则不同。

时间复杂度：O(min(n, m))，最坏情况，结点数最少的那棵树遍历完，就知道是否相同了。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) { // 两空树，相同
            return true;
        }
        if((p == null && q != null) || (p != null && q == null)) { // 一根空，一根不空，不相同
            return false;
        }
        // 两根不为空
        if(p.val != q.val) { // 值不相同，不相同
            return false;
        }
        // 两根相同，左、右子树相同才相同；否则不同
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

6.3、另一棵树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

分析：子问题思想。树为空，没有子树；子树与树相同，是子树；子树与树不相同，子树是不是树的左子树的子树，是则是子树；子树是不是树的右子树的子树，是则是子树；否则不是子树。

时间复杂度：O(m*n)，每遇树中一个结点，就遍历子树是否与之相等。m 个结点比较 m 次，每次比较 n 个子树结点。

class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) { // 两空树，相同
            return true;
        }
        if((p == null && q != null) || (p != null && q == null)) { // 一根空，一根不空，不相同
            return false;
        }
        // 两根不为空
        if(p.val != q.val) { // 值不相同，不相同
            return false;
        }
        // 两根相同，左、右子树相同才相同；否则不同
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) { // 树为空，没有子树
            return false;
        }
        if (isSameTree(root, subRoot)) { // 树和子树相同，是树的子树
            return true;
        }
        if(isSubtree(root.left, subRoot)) { // 是左子树的子树，是树的子树
            return true;
        }
        return isSubtree(root.right, subRoot); // 是右子树的子树，是树的子树；否则不是树的子树
    }
}

6.4、翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

分析：如果为空或者只有一个根节点，不翻转；否则，左子树和右子树交换，继续翻转左子树、右子树。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 如果树为空，或者只有一个根节点，不翻转
        if(root == null || (root.left == null && root.right == null)) {
            return root;
        }
        // 否则左子树和右子树交换
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        // 翻转左子树、右子树
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

6.5、判断平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

平衡二叉树：每一棵子树的左右子树的高度差不超过1。

分析：空树，是平衡二叉树。左子树是平衡二叉树，且右子树是平衡二叉树，左子树的高度和右子树的高度差的绝对值≤1，是平衡二叉树；否则不是。

时间复杂度：O(N^2)，对于树中每个结点，都要求其左、右子树的高度；每次求子树高度，都会遍历整棵子树。

class Solution {

    public int height(TreeNode root) {
        if (root == null) { // 空树，深度为0
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        // 空树是平衡二叉树
        if(root == null) {
            return true;
        }
        // 左子树不是平衡二叉树，或者右子树不是平衡二叉树，则树不是平衡二叉树
        if(!isBalanced(root.left) || !isBalanced(root.right)) {
            return false;
        }
        // 左右子树高度差的绝对值≤1，是平衡二叉树，否则不是
        return Math.abs(height(root.left) - height(root.right)) <= 1;
    }
}

改进：其实，求树的高度就包含了求子树的高度；但是上面的代码重复求了子树的高度。改进思路就是，我们只需求一次树的高度，在此过程中必然历经，求子树、子子树高度，在求到它们高度的之后，马上判断它们的高度差的绝对值是否≤1，它们是否是平衡二叉树。

时间复杂度：O(N)。只求了一次树的高度，遍历了所有结点。

class Solution {

    /**
     * 返回值：-1 表示不为平衡二叉树，大于 -1 表示树的高度。
     */
    private int height(TreeNode root) {
        if (root == null) { // 空树，深度为0
            return 0;
        }
        // 求左、右子树高度
        int leftH = height(root.left);
        int rightH = height(root.right);
        // 求完高度，马上判断是否符合平衡二叉树的要求
        // 左、右子树是否为平衡二叉树
        if(leftH == -1 || rightH == -1) {
            return -1;
        }
        // 左右子树高度差是否符合要求
        if(Math.abs(leftH - rightH) > 1) {
            return -1;
        }
        // 左、右子树符合平衡二叉树要求，返回树的高度
        return Math.max(leftH, rightH) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        // 空树是平衡二叉树
        if(root == null) {
            return true;
        }
        // 如果返回值 > -1，表示是树高度，是平衡二叉树；否则不是
        return height(root) > -1;
    }
}

6.6、判断对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

分析：子问题思路。空树，对称。非空树，对于左、右子树根节点，都为空，则对称；一个为空、一个不为空，则不对称；都不为空，但是值不相等，则不对称；都不为空，且值相等，左根的左子树与右根的右子树对称，且左根的右子树与右根的左子树对称，则树对称；否则不对称。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) { // 空树，对称
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftRoot, TreeNode rightRoot) {
        // 左根、右根都为空，对称
        if(leftRoot == null && rightRoot == null) {
            return true;
        }
        // 左、右根其中一个不为空，另一个为空，不对称
        if((leftRoot == null && rightRoot != null) || (leftRoot != null && rightRoot == null)) {
            return false;
        }
        // 左右根不为空，但值不等，不对称
        if(leftRoot != null && rightRoot != null && leftRoot.val != rightRoot.val) {
            return false;
        }
        // 左根的左子树、右根的右子树对称，且左根的右子树、右根的左子树对称，才对称
        return isSymmetricChild(leftRoot.left, rightRoot.right) && isSymmetricChild(leftRoot.right, rightRoot.left);
    }
}

6.7、先序构建，中序遍历

二叉树遍历_牛客题霸_牛客网

分析：重点在根据先序遍历序列构建二叉树。因为这里告诉了空结点，所以只有一个先序遍历序列也能构建二叉树。

        遍历思想。先序遍历，如果根节点是'#'，则返回 null；如果根节点不是'#'，则创建结点，到下一个字符，创建左子树、创建右子树，最后返回根节点。

import java.util.Scanner;

class TreeNode {
    char value;
    TreeNode left;
    TreeNode right;

    public TreeNode(char value) {
        this.value = value;
    }
}

public class Main {

    public static int i; // 记录字符下标

    // 先序创建树
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i)); // 创建新节点
            i++;
            // 创建左、右子树
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;
    }

    // 中序遍历
    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.value + " ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            i = 0;
            TreeNode root = createTree(str);
            inOrder(root);
        }
    }
}

6.8、最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

分析：根据题目，树中必有p、q两节点。如果 p 在左子树中，q 在右子树中，则 root 为最近公共祖先。

如果 p、q 中存在一个是根结点，则 root 为最近公共祖先。

如果 p、q 都在左子树中，进入左子树找最近公共祖先。

如果 p、q 都在右子树中，进入右子树找最近公共祖先。

时间复杂度：O(N)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果为空树，没有最近公共祖先
        // 必须加此判断，遇到叶子结点，递归函数才能返回 null
        if(root == null) {
            return null;
        }
        // 其中一个是根节点，最近公共祖先是根
        if(p == root || q == root) {
            return root;
        }
        TreeNode leftFather = lowestCommonAncestor(root.left, p, q);
        TreeNode rightFather = lowestCommonAncestor(root.right, p, q);
        // p、q 分布在左、右两子树中，最近公共祖先是根
        if(leftFather != null && rightFather != null) {
            return root;
        }
        // 最近公共祖先在左子树中
        if(leftFather != null) {
            return leftFather;
        }
        // 最近公共祖先在右子树中
        if(rightFather != null) {
            return rightFather;
        }
        // 树中不存在 q、p
        return null;
    }
}

思路2：找到根节点分别到 p、q 的路径，对比路径，找到最近公共祖先。

p 的路径：3、5、6。size=3

q 的路径：3、5、2、4。size=4

q 路径出栈 4-3=1 个元素，得到 3、5、2。

p 、q 同时出栈，不相同则继续同时出栈，相同则找到最近公共祖先。

时间复杂度：O(N^2)，找了两次路径。

class Solution {
    public boolean getPath(TreeNode root, TreeNode target, Stack<TreeNode> stack) {
        if(root == null) { // 空树，没有路径
            return false;
        }
        stack.push(root); // 根节点入栈
        if(root == target) { // 找到目标节点，退出
            return true;
        }
        boolean found = getPath(root.left, target, stack); // 在左子树中寻找路径
        if(found) { // 找到路径，退出
            return true;
        }
        found = getPath(root.right, target, stack); // 在右子树中寻找路径
        if(found) { // 找到路径，退出
            return true;
        }
        stack.pop(); // 路径没找到，根结点出栈
        return false;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root, p, stack); // 寻找 p 的路径
        getPath(root, q, stack2); // 寻找 q 的路径
        // 计算路径长度差，长的路径先出栈差的绝对值长度
        int len = stack.size() - stack2.size();
        if(len < 0) { // 长度差为负，交换两个栈
            Stack<TreeNode> temp = stack;
            stack = stack2;
            stack2 = temp;
            len = -len;
        }
        // 弹出栈中元素，直到长度差为0
        while(len-- != 0) {
            stack.pop();
        }
        // 弹出栈中元素，不相同则继续弹，相同则为最近公共祖先
        while(!stack.isEmpty() && !stack2.isEmpty() && stack.peek() != stack2.peek()) {
            stack.pop();
            stack2.pop();
        }
        return stack.isEmpty()? null : stack.peek(); // 栈为空，没有最近公共祖先
    }
}

6.9、根据前序、中序构造树

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

分析：前序遍历从左往右，找根节点，创建根节点。再在中序遍历中找根节点的位置，区分左右子树。再构建左子树，构建右子树。

class Solution {
    private int preIndex; // 先序序列的根下标

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, inorder.length-1);
    }

    private int findIndex(int[] inorder, int low, int high, int rootVal) {
        for(int i = low; i <= high; i++) {
            if(inorder[i] == rootVal) {
                return i;
            }
        }
        return -1;
    }

    // low、high 为在中序序列中子树的起始、终止下标
    private TreeNode buildTree(int[] preorder, int[] inorder, int low, int high) {
        if(low > high) { // 没有结点了，返回空
            return null;
        }
        int rootVal = preorder[preIndex]; // 根
        TreeNode root = new TreeNode(rootVal); // 创建根结点
        preIndex++;
        int inIndex = findIndex(inorder, low, high, rootVal); // 在中序序列中找根的位置
        // 构建左、右子树
        root.left = buildTree(preorder, inorder, low, inIndex-1);
        root.right = buildTree(preorder, inorder, inIndex+1, high);
        return root;
    }
}

6.10、根据中序、后序遍历构造树

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

分析：方法与 6.9 大致相同，只不过后序序列是从后往前遍历根。后序：左右根，倒着遍历，会先创建右子树。

class Solution {

    private int postIndex; // 后序序列的根下标

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTree(postorder, inorder, 0, inorder.length-1);
    }

    private int findIndex(int[] inorder, int low, int high, int rootVal) {
        for(int i = low; i <= high; i++) {
            if(inorder[i] == rootVal) {
                return i;
            }
        }
        return -1;
    }

    // low、high 为在中序序列中子树的起始、终止下标
    private TreeNode buildTree(int[] postorder, int[] inorder, int low, int high) {
        if(low > high) { // 没有结点了，返回空
            return null;
        }
        int rootVal = postorder[postIndex]; // 根
        TreeNode root = new TreeNode(rootVal); // 创建根结点
        postIndex--;
        int inIndex = findIndex(inorder, low, high, rootVal); // 在中序序列中找根的位置
        // 构建左、右子树
        root.right = buildTree(postorder, inorder, inIndex+1, high);
        root.left = buildTree(postorder, inorder, low, inIndex-1);
        return root;
    }
}

6.11、根据二叉树创建字符串

分析：前序遍历，同一棵子树中的结点会被()包在一起。空树，不打印。非空树，打印根节点，如果左右孩子都为空，什么都不打印。如果左孩子不为空，右孩子为空，打印(，遍历左子树，打印)。如果左孩子为空，右孩子不为空，打印()(，遍历右子树，打印)。如果左右孩子都不为空，打印(，遍历左子树，打印)(，遍历右子树，打印)。

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2str(root, str);
        return str.toString();
    }

    public void tree2str(TreeNode root, StringBuilder str) {
        // 空树，不打印
        if (root == null) {
            return;
        }
        str.append(root.val); // 打印根节点
        // 如果左孩子不为空，打印(，遍历左子树，打印)
        if (root.left != null) {
            str.append('(');
            tree2str(root.left, str);
            str.append(')');
            // 如果右孩子为空，什么都不打印
            // 如果右孩子不为空，打印(，遍历右子树，打印)
            // if(root.right != null) {
            // str.append('(');
            // tree2str(root.right, str);
            // str.append(')');
            // }
        } else {
            // 如果右子树为空，什么都不打印
            // 如果右子树不为空，打印()，打印(，遍历右子树，打印)
            if (root.right != null) {
                str.append("()");
                // str.append('(');
                // tree2str(root.right, str);
                // str.append(')');
            }
        }
        if (root.right != null) {
            str.append('(');
            tree2str(root.right, str);
            str.append(')');
        }
    }
}