⭐️前面的话⭐️

本篇文章带大家认识数据结构——二叉树，树是一种非线性的数据结构，它是由有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆华为云首发时间：🌴2022年5月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：📚《Java核心技术卷1》，📚《数据结构》，📚《Java编程思想》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

2.二叉树的应用与创建

2.1二叉树的应用

2.1.1相同的二叉树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

🎉解题思路：
(1)如果两棵树的根结点都为空，则两棵树相同。
(2)如果两棵树的根结点有一个为空，则两棵树必然不相同。
(3)如果两棵树都不为空，则判断根结点的值是否相同，不相同则这两棵树必然不相同。
(4)如果两棵树根结点的值相同，则需要判断两棵树的左右子树是否相同，如果相同则这两棵树相同。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == q && p == null) {
            return true;                                                            //(1)
        }
        if (p == null || q == null) {
            return false;                                                           //(2)
        }
        if (p.val != q.val) {
            return false;                                                           //(3)
        }else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);      //(4)
        }
    }
}

在线练习：
100. 相同的树

2.1.2另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

• root 树上的节点数量范围是 [1, 2000]
• subRoot 树上的节点数量范围是 [1, 1000]
• -104 <= root.val <= 104
• -104 <= subRoot.val <= 104

🎉解题思路：
判断一棵树是否为另一棵树的子树我们可以基于判断两棵树是否相同去做。
(1)如果root与subRoot的地址相同，则说明两棵树是同一棵树，那么subRoot肯定是root的子树。
(2)如果root与subRoot有一棵树是空，那么subRoot必然不是root的子树。
(3)如果root与subRoot相同，那么subRoot肯定是root的子树。
(4)如果root的子树含有与subRoot相同的树，那么subRoot肯定是root的子树。

class Solution {
	//判断两棵树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == q && q == null) return true;			
        if (p == null || q == null) return false;

        if (p.val != q.val) {
            return false;
        } 
        else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == subRoot) return true;
        if (root == null || subRoot == null) return false;
        //整棵树是否与subRoot相同
        if (isSameTree(root, subRoot)) return true;
        //subRoot是否是左子树的子树
        if (isSubtree(root.left, subRoot)) return true;
        //subRoot是否是右子树的子树
        if (isSubtree(root.right, subRoot)) return true;
        //上面都不满足，则subRoot不是该树的子树
        return false;
    }
}

在线练习：
572. 另一棵树的子树

2.1.3对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

🎉解题思路：
判断一棵树是否是对称二叉树，其实就是判断这棵树的左右子树是否相同，如果相同则该二叉树对称，反之不对称，当然如果这棵二叉树是空树，那这棵树也是对称的。所以这又回到比较两棵树是否相等这个题目上去了。
(1)如果二叉树为空，返回true。
(2)比较左右子树是否相等，相等返回true，否则返回false。

class Solution {
    //(2)判断左右子树是否相同
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if (leftTree == rightTree && leftTree == null) {
            return true;
        }
        if (leftTree == null || rightTree == null) {
            return false;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;       //(1)
        return isSymmetricChild(root.left,root.right);//(2)
    }
}

在线练习：
101. 对称二叉树

2.1.4镜像二叉树

所谓镜像二叉树，就是将二叉树的所有左右子树翻转一下。
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

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

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

🎉解题思路：
(1)如果该树为空树，返回null。
(2)交换左右子树的根结点。
(3)交换左子树的左右子树，交换右子树的左右子树。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;//(1)

        TreeNode tmp = root.left;
        root.left = root.right;//(2)
        root.right = tmp;
        mirrorTree(root.right);//(3)
        mirrorTree(root.left);//(3)
        return root;
    }
}

在线练习：
226. 翻转二叉树
剑指 Offer 27. 二叉树的镜像

2.1.5平衡二叉树

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

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

🎉解题思路：
(1)如果树为空，则这棵树是平衡二叉树。
(2)获取该树左右子树的高度差的绝对值，如果大于1，则这棵树肯定不是平衡二叉树。
(3)如果高度差绝对值不大于1，再判断该树的左右子树是否都是平衡二叉树，如果是，则这一整棵树是平衡二叉树。

所以这道题最终回到了求二叉树的高度上来。

class Solution {
    //获取二叉树的高度
    public int maxDeep(TreeNode subtree) {
        if (subtree == null) {
            return 0;
        }
        return 1 + Math.max(maxDeep(subtree.left), maxDeep(subtree.right));
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;            //(1)
        }
        int ret = Math.abs(maxDeep(root.left) - maxDeep(root.right));       //(2)
        if (ret <= 1 && isBalanced(root.left) && isBalanced(root.right)) {  //(3)
            return true;
        }
        return false;
    }
}

在线练习：
110. 平衡二叉树
剑指 Offer 55 - II. 平衡二叉树
面试题 04.04. 检查平衡性

2.1.6二叉树的最近公共祖先

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

🎉解题思路：
递归思路：
(1)如果为空树返回null。
(2)如果p，q结点的数据均与根结点root相同，则最近公共祖先为root。
(3)如果p，q都在左子树或右子树，则最近公共祖先也在左子树或右子树。
(4)如果p，q位于不同的左右子树上，则最近公共祖先为root。

对于(3)(4)两点，我们可以分别去左右子树找p，q结点，如果在左右子树均找到，说明思路(4)成立，如果在左右子树中只找到一个，就说明思路(3)成立，如果在左右子树都没有找到，就说明p，q在root这棵二叉树上没有公共祖先。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;                                            //(1)
        }
        if (q.val == root.val || p.val == root.val) {
            return root;                                            //(2)
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);     
        TreeNode right = lowestCommonAncestor(root.right, p, q);    
        if (left != null && right != null) {
            return root;                                            //(4)
        }else if (left != null) {
            return left;                                            //(3)
        } else if (right != null) {
            return right;                                           //(3)
        }else {
            return null;                                            //不存在最近祖先
        }
    }
}

非递归思路：
可以利用两个栈分别存储root->p, root->q的二叉树路径，然后将元素多的那一个栈内的元素出栈，直到与另一个栈的元素数量相等，最后两栈同时出栈，并比较栈顶元素，如果相等，则相等的那个结点就是p，q的最近公共祖先，直到栈为空，如果栈为空还没有找到，p，q在root这棵树上没有公共祖先。

(1)使用两个栈分别存储root->p, root->q的二叉树路径。
(2)寻找root->p, root->q的二叉树路径。
(3)调整元素数量较多的栈，使其元素数量与另一个栈相等。
(4)两栈同时出栈并比较栈顶元素，相等的元素结点即为最近公共结点。

class Solution {
    private boolean findPath(TreeNode root, TreeNode goal, Stack<TreeNode> stack) {
        if (root == null) return false;
        stack.push(root);//先将该结点入栈，再判断root->goal路径上是否含有该结点，若没有将该结点出栈
        if (root == goal) return true;
        if (findPath(root.left, goal, stack)) return true;//确定左子树路径
        if (findPath(root.right, goal, stack)) return true;//确定右子树路径
        stack.pop();//该节点左右子树都没goal结点路径，说明该结点也不是root->goal路径上的结点
        return false;//说明没有找到路径
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        Stack<TreeNode> stack1  = new Stack<>();                    //(1)
        Stack<TreeNode> stack2  = new Stack<>();                    //(1)
        findPath(root, p, stack1);                                  //(2)
        findPath(root, q, stack2);                                  //(2)

        int size1 = stack1.size();                  
        int size2 = stack2.size();
        if (size1 > size2) {
            int size = size1 - size2;
            while (size > 0) {
                stack1.pop();                                       //(3)
                size--;
            }
            while (!stack1.isEmpty() && !stack2.isEmpty()) {
                if (stack1.peek() == stack2.peek()) {
                    return stack1.pop();                            //(4)
                }
                stack1.pop();
                stack2.pop();
            }
        } else {
            int size = size2 - size1;
            while (size > 0) {
                stack2.pop();                                      //(3)
                size--;
            }
            while (!stack1.isEmpty() && !stack2.isEmpty()) {
                if (stack1.peek() == stack2.peek()) {
                    return stack1.pop();                            //(4)
                }
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }
}

关于(2)寻找root->p, root->q的二叉树路径的思路（递归）：
(1)如果目标的二叉树为空，那么肯定没有路径。
(2)创建一个栈，用于存放路径，先假设路径存在并把这条路径上的结点入栈，然后顺着这个路径寻找p或者q，如果没找到，将这条路径上的结点出栈，换另外一条路径寻找。
(3)根据(2)的需求，需设置函数返回值为boolean，以判断是否找到正确的路径。

private boolean findPath(TreeNode root, TreeNode goal, Stack<TreeNode> stack) {
        if (root == null) return false;						//(1)
        stack.push(root);									//(2)先将该结点入栈，再判断root->goal路径上是否含有该结点，若没有将该结点出栈
        if (root == goal) return true;
        if (findPath(root.left, goal, stack)) return true;	//(2)确定左子树路径
        if (findPath(root.right, goal, stack)) return true;	//(2)确定右子树路径
        stack.pop();										//(2)该节点左右子树都没goal结点路径，说明该结点也不是root->goal路径上的结点
        return false;										//(3)说明没有找到路径
}

在线练习：
235. 二叉搜索树的最近公共祖先
236. 二叉树的最近公共祖先
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
剑指 Offer 68 - II. 二叉树的最近公共祖先

2.2二叉树的创建

2.2.1根据字符串创建二叉树

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述:

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

示例:

输入：

abc##de#g##f###

输出：

c b e g d f a 

🎉解题思路：
(1)注意题目需要多组输入。
(2)构建二叉树结点。
(3)读取字符串，根据前序遍历的顺序构建二叉树。遇到非#符号，创建一个结点并存入目标值，然后按照前序遍历的顺序构建该树的左子树，右子树，遇到#符号，相当于遇到二叉树的空，将字符串下标加1返回即可。
(4)使用一个成员变量，对字符串进行遍历，因为在递归的过程中，设置局部变量会被销毁。每构建一个二叉树应将该成员变量置为0。
(5)中序遍历输出已经创建好的二叉树。

import java.util.*;
class TreeNode {                                //(2)
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val) {
        this.val = val;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int index = 0;                            //(4)
    public static TreeNode creatTree(String str) {
        TreeNode node = null;
        char val = str.charAt(index);                        //(3)
        if (val != '#') {
            node = new TreeNode(val);                        //(3)
            index++;
            node.left = creatTree(str);                        //(3)
            node.right = creatTree(str);                       //(3)
        } else {
            index++;
        }
        return node;
    }
    public static void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s = in.nextLine();                        //(1)
            index = 0;                                       //(4)
            TreeNode root = creatTree(s);                    //(2)
            inOrder(root);                                   //(5)
            System.out.println();
        }
    }
}

在线练习：
KY11 二叉树遍历

2.2.2根据前序遍历与中序遍历创建二叉树

根据前序遍历我们可以确定二叉树的根结点，前序遍历的顺序是根，左子树，右子树，所以创建树的时候，应该以根，左子树，右子树的顺序创建，根据中序遍历我们能够得到一个根结点的左右子树。

二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为___。
根据前序遍历结果，第一个遍历的结点为整棵二叉树的根结点，所以二叉树根结点为E，根据中序遍历能够确定该根结点的左右子树，所以HFI为E的左子树中序遍历序列，JKG为E右子树的中序遍历序列，以此类推能够确定整棵树所有的左子树与右子树。下图为根据前序遍历序列和中序遍历序列创建的二叉树：

尝试使用编程根据前序遍历与中序遍历创建二叉树：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

🎉解题思路：
(1)创建一棵二叉树的根结点。
(2)根据前序遍历数组找到根结点，通过该根节点取中序遍历数组确定该根节点的左右子树，该根结点左边的中序遍历序列为该结点的左子树，右边的中序遍历序列为该结点的右子树。
(3)通过分而治之的思想，去创建该树的左子树与右子树。
(4)假设遍历前序遍历数组的下标为pi，中序遍历数组的起始序列结点下标为is，结束序列结点下标为ie，所创建树的根结点为ri，则创建一棵树的左子树中序遍历序列下标范围为[is, ri-1]，右子树中序遍历序列下标范围为[ri+1, ie]，通过前序遍历的顺序去创建一棵二叉树的根，左子树和右子树。

class Solution {
    private int preIndex;                                                           //前序遍历序列数组下标，需使用成员变量
    private TreeNode creatTree(int[] preorder, int[] inorder, int instart, int inend) {
        if (instart > inend) return null;                                           //说明所创建结点为空
        TreeNode root = new TreeNode(preorder[preIndex]);                           //(1)
        int rootIndex = findOfInorder(inorder, instart, inend, preorder[preIndex]);//(2)找到中序遍历对应根节点的下标
        preIndex++;                                                                 //为下一个根结点的创建做准备
        //根据前序遍历顺序先找到root的左子树再找到root的右子树
        root.left = creatTree(preorder, inorder, instart, rootIndex - 1);           //(3)(4)
        root.right = creatTree(preorder, inorder, rootIndex + 1, inend);            //(3)(4)
        return root;
    }
    private int findOfInorder(int[] inorder, int instart, int inend, int key) {
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == key) return i;                                        //(2)
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) return null;
        return creatTree(preorder, inorder, 0, inorder.length - 1);
    }
}

在线练习：
105. 从前序与中序遍历序列构造二叉树

2.2.3根据中序遍历和后序遍历创建二叉树

根据后序遍历我们可以确定二叉树的根结点，但是要注意，后序遍历是最后才遍历根结点的，所以根结点在序列的末端，所以需要从右向左依次读取后续遍历的序列，得到根结点的顺序是整棵二叉树的根，右子树，左子树，所以根据后序遍历和中序遍历创建二叉树的顺序是根结点，右子树，左子树，根据中序遍历我们能够得到一个根结点的左右子树。

设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为_____。

根据二叉树中序遍历序列：badce，后序遍历序列：bdeca，能够确定二叉树序列，如上图。
所以二叉树前序遍历序列为abcde

尝试使用编程根据前序遍历与中序遍历创建二叉树：
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

🎉解题思路：
这题相对与根据前序遍历和中序遍历创建二叉树值改变了一点，也就是将前序遍历变为后续遍历，而我们知道可以根据后序遍历序列从右向左读取根，右子树，左子树，所以该题只需改变后序遍历数组遍历顺序和二叉树创建顺序。
(1)创建一棵二叉树的根结点。
(2)根据后序遍历数组从右向左找到根结点，通过该根节点取中序遍历数组确定该根结点的左右子树，该根结点左边的中序遍历序列为该结点的左子树，右边的中序遍历序列为该结点的右子树。
(3)通过分而治之的思想，去创建该树的右子树与左子树。
(4)假设 从右向左 遍历后序遍历数组的下标为pi，中序遍历数组的起始序列结点下标为is，结束序列结点下标为ie，所创建树的根结点为ri，则创建一棵树的左子树中序遍历序列下标范围为[is, ri-1]，右子树中序遍历序列下标范围为[ri+1, ie]，通过逆后序遍历的顺序去创建一棵二叉树的根，右子树和左子树。

class Solution {
    private int postIndex;                                                                                  //后序遍历序列数组下标，需使用成员变量                       
    private TreeNode creatTree(int[] inorder, int instart, int inend, int[] postorder) {
        if (instart > inend) return null;
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findOfInorder(inorder, instart, inend, postorder[postIndex]);//(2)找到中序遍历对应根节点的下标
        postIndex--;                                                        //为创建下一个根结点做准备
        //根据后序遍历顺序先找到root的右子树再找到root的左子树
        root.right = creatTree(inorder, rootIndex + 1, inend, postorder);   //(3)(4)
        root.left = creatTree(inorder, instart, rootIndex - 1, postorder);  //(3)(4)
        return root;
    }
    private int findOfInorder(int[] inorder, int instart, int inend, int key) {
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == key) return i;                                //(2)
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) return null;
        postIndex = postorder.length - 1;                                   //从右向左遍历后序遍历数组
        return creatTree(inorder, 0, inorder.length - 1,postorder);
    }
}

在线练习：
106. 从中序与后序遍历序列构造二叉树

总结：
同时给定一棵二叉树的先序序列和中序序列能唯一确定这棵二叉树。
同时给定一棵二叉树的中序序列和后序序列能唯一确定这棵二叉树。
同时给定一棵二叉树的先序序列和后序序列不能唯一确定这棵二叉树。

2.2.4将二叉搜索树改为双链表

如果想要知道如何将搜索二叉树改造成双链表，得知道什么是二叉搜索树。
二叉搜索树是一种特殊的二叉树，又称二叉查找树，二叉排序树，它有几个特点：

• [x] 如果左子树存在，则左子树每个结点的值均小于根结点的值。
• [x] 如果右子树存在，则右子树每个结点的值均大于根结点的值。
• [x] 中序遍历二叉搜索树，得到的序列是依次递增的。
• [x] 二叉搜索树的左右子树均为二叉搜索树。

下面我们来看一道例题，来说明如何将二叉树转换为双链表：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

🎉解题思路：
首先根据题意我们需要将二叉搜索树转换为一个升序排列的循环双向链表，我们可以根据二叉搜索树中序遍历得到一个排序的序列这一特点，使用中序遍历进行遍历二叉树。
(1)使用一个引用prev(初始为null)用来保存中序遍历的前一个结点，使用引用head来记录二叉搜索树的最小结点，即双链表的头结点。
(2)如果prev为null，说明当前遍历的结点为二叉搜索树的最小结点（构造双链表的第一个结点），使用head记录该结点。
(3)如果prev不为null，说明当前遍历的结点在构造的双链表中存在前驱和后继，为了使改造对中序遍历影响最小，我们将二叉树结点的left作为链表的前驱，二叉树结点的right作为链表的后继，所以当prev不为null时，将prev的后继指向当前结点，当前结点的前驱置为prev。
(4)更新prev为当前结点，继续中序遍历剩下结点，重复上述操作，返回值为当前结点。
(5)双链表改造完成后，需要找到链表最后一个结点，将其与第一个结点连接，获得一个循环双链表。

class Solution {
    private Node prev;                              //记录前一个遍历结点
    private Node head;                              //记录头结点
    private Node inorderToList(Node root) {
        if (root == null) return null;
        //二叉搜索树中序遍历等有序序列，left指向前驱，right指向后继
        inorderToList(root.left);
        root.left = prev;                           //(3)
        if (prev != null) prev.right = root;        //(3)
        else head = root;                           //(2)
        prev = root;                                //(4)
        inorderToList(root.right);
        return root;                                //(4)
    }
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Node tail = inorderToList(root);//最终返回的结点为根结点
        while (tail.right != null) {
            tail = tail.right;                  //(5)
        }
        head.left = tail;                       //(5)
        tail.right = head;                      //(5)
        return head;
    }
}

在线练习：
剑指 Offer 36. 二叉搜索树与双向链表
JZ36 二叉搜索树与双向链表

2.2.5将二叉树改为单链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

进阶： 你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

🎉解题思路：
(1)如果根结点的左子树为空，将根结点变为右子树根结点，直到该结点有左子树，找到左子树最右边的结点mostRight。
(2)将右子树拼接到mostRight右边。
(3)将根结点的right指向左子树，根结点的left置null，将根结点变为新右子树根结点，重复上述操作直到结点为空，这样二叉树就完全转换成单链表了。

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        while (root != null) {
            if (root.left == null) {
                root = root.right;                      //(1)
            } else {
                TreeNode mostRight = root.left;
                while (mostRight.right != null) {
                    mostRight = mostRight.right;        //(1)找到左子树根结点的最右端
                }
                mostRight.right = root.right;           //(2)将右子树拼接到最右端
                root.right = root.left;                 //(2)
                root.left = null;                       //(2)
                root = root.right;                      //(3)
            }
        }
    }
}

在线练习：
114. 二叉树展开为链表

2.2.6根据二叉树创建字符串

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1:

输入: 二叉树: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

输出: "1(2(4))(3)"

解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。

示例 2:

输入: 二叉树: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

输出: "1(2()(4))(3)"

解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

🎉解题思路：
(1)按照前序遍历的顺序对二叉树进行遍历，遍历之前需要判断结点左右子树存在情况，根据不同情况添加不同的括号，可以使用StringBuilder对象来对字符串进行组装。
(2)首先在StringBuilder对象添加根结点数据，如果根结点的左子树不为空，加左括号，左子树数据，右括号，如果为空，就判断右子树是否存在，如果存在加上一对括号，不存在则什么都不用做。
(3)遍历完左子树后，考虑右子树是否为空，如果不为空，加左括号，加右子树数据，加右括号，如果为空什么都不用做。

class Solution {
    private void treeToString(TreeNode root, StringBuilder sb) {
        sb.append(root.val);                                //(1)

        if (root.left != null) {
            sb.append("(");
            treeToString(root.left, sb);                    //(2)
            sb.append(")");
        } else {
            if (root.right == null) return;                 //(2)
            sb.append("()");
        }

        if (root.right != null) {
            sb.append("(");
            treeToString(root.right, sb);                   //(3)
            sb.append(")");
        } else {
            return;                                         //(3)
        }
    }
    public String tree2str(TreeNode root) {
        if (root == null) return null;
        StringBuilder sb = new StringBuilder();             //(1)
        treeToString(root, sb);                             
        return sb.toString();
    }
}

在线练习：
606. 根据二叉树创建字符串

本文到这就该结束了，下期再见！