力扣刷题：二叉树篇

电玩女神 2022-10-16 09:40 211阅读 0赞

### 目录 ###

*  100. 相同的树
 *   *  题目介绍
     *  题目实现
 *  101. 对称二叉树
 *   *  题目介绍
     *   *   *  \[剑指 Offer 28. 对称的二叉树\](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/)
     *  题目实现
 *  102. 二叉树的层序遍历
 *   *  题目介绍
     *  题目实现
 *  104. 二叉树的最大深度
 *   *  题目介绍
     *   *   *  \[剑指 Offer 55 - I. 二叉树的深度\](https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/)
     *  题目实现
 *  105. 从前序与中序遍历序列构造二叉树
 *   *  题目介绍
     *   *   *  \[剑指 Offer 07. 重建二叉树\](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/)
     *  题目实现
 *  106. 从中序与后序遍历序列构造二叉树
 *   *  题目实现
     *  题目介绍
 *  110. 平衡二叉树
 *   *  题目介绍
     *   *   *  \[剑指 Offer 55 - II. 平衡二叉树\](https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/)
             *  \[剑指 Offer 55 - I. 二叉树的深度\](https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/)
     *  题目实现
 *  117. 填充每个节点的下一个右侧节点指针 II
 *   *  题目介绍
     *  题目实现
 *  124. 二叉树中的最大路径和
 *   *  题目介绍
     *  题目实现
 *  144. 二叉树的前序遍历
 *   *  题目介绍
     *  题目实现
 *  145. 二叉树的后序遍历
 *   *  题目介绍
     *  题目实现
 *  226. 翻转二叉树
 *   *  题目介绍
     *  题目实现
 *  236. 二叉树的最近公共祖先
 *   *  题目介绍
     *   *   *  \[剑指 Offer 68 - I. 二叉搜索树的最近公共祖先\](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/)
             *  \[剑指 Offer 68 - II. 二叉树的最近公共祖先\](https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/)
     *  题目实现
 *  297. 二叉树的序列化与反序列化
 *   *  题目介绍
     *   *   *  \[449. 序列化和反序列化二叉搜索树\](https://leetcode-cn.com/problems/serialize-and-deserialize-bst/)
             *  \[剑指 Offer 37. 序列化二叉树\](https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/)
             *  \[144. 二叉树的前序遍历\](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
     *  题目实现
 *  572. 另一棵树的子树
 *   *  题目介绍
     *  题目实现
 *  617. 合并二叉树
 *   *  题目介绍
     *  题目实现
 *  637. 二叉树的层平均值
 *   *  题目介绍
     *   *   *  \[102. 二叉树的层序遍历\](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
     *  题目实现
 *  654. 最大二叉树
 *   *  题目介绍
     *  题目实现
 *  94. 二叉树的中序遍历
 *   *  题目介绍
     *  题目实现
 *  965. 单值二叉树
 *   *  题目介绍
     *  题目实现
 *  98. 验证二叉搜索树
 *   *  题目介绍
     *   *   *  \[面试题 04.05. 合法二叉搜索树\](https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/)
     *  题目实现
 *  99. 恢复二叉搜索树
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 07. 重建二叉树
 *   *  题目介绍
     *   *   *  \[105. 从前序与中序遍历序列构造二叉树\](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
     *  题目实现
 *  剑指 Offer 28. 对称的二叉树
 *   *  题目介绍
     *   *   *  \[101. 对称二叉树\](https://leetcode-cn.com/problems/symmetric-tree/)
     *  题目实现
 *  剑指 Offer 32 - I. 从上到下打印二叉树
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 33. 二叉搜索树的后序遍历序列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 37. 序列化二叉树
 *   *  题目介绍
     *   *   *  \[297. 二叉树的序列化与反序列化\](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/)
     *  题目实现

--------------------

# 100. 相同的树 #

## 题目介绍 ##

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

**示例 1：**

![9fa10c77dbb951f3e6d1b80b115dc2ff.png][]

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

**示例 2：**

![1c681f82a045bac20a1d156bb356dc7f.png][]

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

**示例 3：**

![981bac584ca594d969b56fadca15237a.png][]

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

**提示：**

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/same-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public boolean isSameTree(TreeNode p, TreeNode q) { 
            if (p == null && q == null) return true;
            if (p == null || q == null) return false;
            return (p.val == q.val) && (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
        }
    }

# 101. 对称二叉树 #

## 题目介绍 ##

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

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

1
       / \
      2   2
     / \ / \
    3  4 4  3

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

1
       / \
      2   2
       \   \
       3    3

**进阶：**

你可以运用递归和迭代两种方法解决这个问题吗？

**相同题目：**

*  #### [剑指 Offer 28. 对称的二叉树][Offer 28.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/symmetric-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

*  **对称二叉树定义：** 对于树中 **任意两个对称节点** L 和 R ，一定有：

![e672f9e1b99f1aede8a6aed942397ec6.png][]

*  根据以上规律，考虑从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树。

![9c67aacf604acf4fd7900ac9cdab5ddc.png][]

**算法流程：**

**`isSymmetric(root)` ：**

*  **特例处理：** 若根节点 `root` 为空，则直接返回 true 。
 *  **返回值：** 即 `recur(root.left, root.right)` ;

**`recur(L, R)` ：**

*  **终止条件：**

![66f92634240a8c3b4fd6505b82014f82.png][]

*  **递推工作：**

![3a55af3a2e181a48953a76f95a398ab9.png][]

*  **返回值：** 两对节点都对称时，才是对称树，因此用与逻辑符 `&&` 连接。

class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            return root == null ? true : recur(root.left, root.right);
        }
    
        public boolean recur(TreeNode L, TreeNode R) { 
            if (L == null && R == null) return true;
            if (L == null || R == null || L.val != R.val) return false;
            return recur(L.left, R.right) && recur(L.right, R.left);
        }
    }

# 102. 二叉树的层序遍历 #

## 题目介绍 ##

给你一个二叉树，请你返回其按 **层序遍历** 得到的节点值。 （即逐层地，从左到右访问所有节点）。

**示例：**  
二叉树：`[3,9,20,null,null,15,7]`

3
       / \
      9  20
        /  \
       15   7

返回其层序遍历结果：

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![0b20a5287ecd8a235ea5f09793e7ed0a.png][]

public List<List<Integer>> levelOrder(TreeNode root) { 
        // 保存最终结果
        List<List<Integer>> levels = new ArrayList<>();
        // 进行临界判断
        if (root == null) return levels;
        // 创建一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 加入指定结点
        queue.offer(root);
        // 循环弹出遍历
        while (!queue.isEmpty()) { 
            // 创建用于保存当前这一层的 level 集合对象
            List<Integer> level = new ArrayList<>();
    
            int currSize = queue.size();
            for (int i = 0; i < currSize; i++) { 
                // 从队列中弹出一个结点，保存当前结点的信息
                TreeNode node = queue.poll();
                level.add(node.val);
                // 判断当前结点还有没有左子结点，有的话入队
                if (node.left != null) { 
                    queue.offer(node.left);
                }
                // 判断当前结点还有没有右子结点，有的话入队
                if (node.right != null) { 
                    queue.offer(node.right);
                }
            }
    
            levels.add(level);
        }
        // 返回最终结果
        return levels;
    }

# 104. 二叉树的最大深度 #

## 题目介绍 ##

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

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

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

**示例：**

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

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 3 。

**相同题目：**

*  #### [剑指 Offer 55 - I. 二叉树的深度][Offer 55 - I.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

如果根节点为空，则最大深度为0。如果根节点不空，计算左子树的最大深度，计算右子树的最大深度，当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1。

class Solution { 
        public int maxDepth(TreeNode root) { 
            if (root == null) return 0;
            // 计算root节点左子树的最大深度
            int left = maxDepth(root.left);
            // 计算root节点右子树的最大深度
            int right = maxDepth(root.right);
            // 比较左子树 和 右子树最大深度
            return Math.max(left + 1, right + 1);
        }
    }

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

## 题目介绍 ##

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

**示例 1：**

![ff3a53d9fd4cda56349a97000cc0d833.png][]

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    Output: [3,9,20,null,null,15,7]

**示例 2：**

Input: preorder = [-1], inorder = [-1]
    Output: [-1]

**提示：**

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

**相同题目：**

*  #### [剑指 Offer 07. 重建二叉树][Offer 07.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        private Map<Integer, Integer> indexMap = new HashMap<>();
    
        public TreeNode buildTree(int[] preorder, int[] inorder) { 
            int n = inorder.length;
            for (int i = 0; i < n; i++) { 
                indexMap.put(inorder[i], i);
            }
            return buildSubTree(preorder, inorder, 0, n - 1, 0, n - 1);
        }
    
        private TreeNode buildSubTree(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) { 
            //递归的终止
            if (preorderLeft > preorderRight) return null;
            //获取根元素
            int rootValue = preorder[preorderLeft];
            //定位根节点
            Integer inorderRoot = indexMap.get(rootValue);
            //构造根节点
            TreeNode root = new TreeNode(rootValue);
            //左元素个数
            int size = inorderRoot - inorderLeft;
            //构造左子树
            root.left = buildSubTree(preorder, inorder, preorderLeft + 1, preorderLeft + size, inorderLeft, inorderRoot - 1);
            //构造右子树
            root.right = buildSubTree(preorder, inorder, preorderLeft + size + 1, preorderRight, inorderRoot + 1, inorderRight);
            //返回根节点
            return root;
        }
    }

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

## 题目实现 ##

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

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

例如，给出

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

返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目介绍 ##

class Solution { 
        private Map<Integer, Integer> indexMap = new HashMap<>();
    
        public TreeNode buildTree(int[] inorder, int[] postorder) { 
            int n = inorder.length;
            for (int i = 0; i < n; i++) { 
                indexMap.put(inorder[i], i);
            }
            return buildSubTree(postorder, inorder, 0, n - 1, 0, n - 1);
        }
    
        private TreeNode buildSubTree(int[] postorder, int[] inorder, int postorderLeft, int postorderRight, int inorderLeft, int inorderRight) { 
            //递归的终止
            if (postorderLeft > postorderRight) return null;
            //获取根元素
            int rootValue = postorder[postorderRight];
            //定位根节点
            Integer inorderRoot = indexMap.get(rootValue);
            //构造根节点
            TreeNode root = new TreeNode(rootValue);
            //右元素个数
            int size = inorderRight - inorderRoot;
            //构造左子树
            root.left = buildSubTree(postorder, inorder, postorderLeft, postorderRight - size - 1, inorderLeft, inorderRoot - 1);
            //构造右子树
            root.right = buildSubTree(postorder, inorder, postorderRight - size, postorderRight - 1, inorderRoot + 1, inorderRight);
            //返回根节点
            return root;
        }
    }

# 110. 平衡二叉树 #

## 题目介绍 ##

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

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

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

**示例 1：**

![5d18a5d96c15f7f06b7833b3b0ccf6ad.png][]

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

**示例 2：**

![0cd152e25159d8276429417d471a1a8d.png][]

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

**示例 3：**

输入：root = []
    输出：true

**提示：**

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

**相同题目：**

*  #### [剑指 Offer 55 - II. 平衡二叉树][Offer 55 - II.] ####

**用到题目：**

*  #### [剑指 Offer 55 - I. 二叉树的深度][Offer 55 - I.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/balanced-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

**算法流程：**

**`recur(root)` 函数：**

*  **返回值：**

![f7e8ab02cb555ef1017905de2c9c35a7.png][]

*  **终止条件：**

![54cda28cb2cfac46c1e39ba0cce77eff.png][]

**`isBalanced(root)` 函数：**

*  **返回值：** 若 `recur(root) != -1` ，则说明此树平衡，返回 `true` ； 否则返回 `false` 。

class Solution { 
        public boolean isBalanced(TreeNode root) { 
            return recur(root) != -1;
        }
    
        private int recur(TreeNode root) { 
            if (root == null) return 0;
            int left = recur(root.left);
            if (left == -1) return -1;
            int right = recur(root.right);
            if (right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
        }
    }

另外一种，根节点的左右子树高度差<=1 + 左子树是平衡二叉树 +右子树是平衡二叉树：

class Solution { 
        public boolean isBalanced(TreeNode root) { 
            if (root == null) return true;
            return (Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) && isBalanced(root.left) && isBalanced(root.right);
        }
    
        public int maxDepth(TreeNode root) { 
            if (root == null) return 0;
            // 计算root节点左子树的最大深度
            int left = maxDepth(root.left);
            // 计算root节点右子树的最大深度
            int right = maxDepth(root.right);
            // 计算root节点右子树的最大深度
            return Math.max(left + 1, right + 1);
        }
    }

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

## 题目介绍 ##

给定一个二叉树

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

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

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

**进阶：**

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

**示例：**

![8ea29f3c8e411003619e1a3a1ad7357d.png][]

输入：root = [1,2,3,4,5,null,7]
    输出：[1,#,2,3,#,4,5,7,#]
    解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

**提示：**

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

这道题希望我们把二叉树各个层的点组织成链表，一个非常直观的思路是层次遍历。

class Solution { 
        public Node connect(Node root) { 
            if (root == null) return null;
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) { 
                int n = queue.size();
                Node last = null;
                for (int i = 0; i < n; i++) { 
                    Node first = queue.poll();
                    if (first.left != null) queue.offer(first.left);
                    if (first.right != null) queue.offer(first.right);
                    if (i != 0) last.next = first;
                    last = first;
                }
            }
            return root;
        }
    }

# 124. 二叉树中的最大路径和 #

## 题目介绍 ##

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

**示例 1：**

![52c3fd6da2b3e199da484e8afcaad142.png][]

输入：root = [1,2,3]
    输出：6
    解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

**示例 2：**

![8e6c4c32c18f8604e73e0c5a538b6a57.png][]

输入：root = [-10,9,20,null,null,15,7]
    输出：42
    解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

**提示：**

*  树中节点数目范围是 \[1, 3 \* 104\]
 *  \-1000 <= Node.val <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，该函数的计算如下。

*  空节点的最大贡献值等于 0。
 *  非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。

例如，考虑如下二叉树。

-10
       / \
      9  20
        /  \
       15   7

叶节点 9、15、7 的最大贡献值分别为 9、15、7。

得到叶节点的最大贡献值之后，再计算非叶节点的最大贡献值。节点 20 的最大贡献值等于 20+max(15,7)=35，节点 −10 的最大贡献值等于 −10+max(9,35)=25。

上述计算过程是递归的过程，因此，对根节点调用函数 maxGain，即可得到每个节点的最大贡献值。

根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。

class Solution { 
        private int maxSum = Integer.MIN_VALUE;
    
        public int maxPathSum(TreeNode root) { 
            maxGain(root);
            return maxSum;
        }
    
        public int maxGain(TreeNode root) { 
            if (root == null) return 0;
            int left = Math.max(0, maxGain(root.left));
            int right = Math.max(0, maxGain(root.right));
            maxSum = Math.max(maxSum, left + right + root.val);
            return Math.max(left, right) + root.val;
        }
    }

# 144. 二叉树的前序遍历 #

## 题目介绍 ##

给你二叉树的根节点 `root` ，返回它节点值的 **前序** 遍历。

**示例 1：**

![433a9a16d4435abcbf764e0ac7b099bd.png][]

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

**示例 2：**

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

**示例 3：**

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

**示例 4：**

![e22679e4c0122466be5a1bac20ee5fd9.png][]

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

**示例 5：**

![e9c0faa94c3e835387b847ce55f9f0e9.png][]

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

**提示：**

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![a331ea6a6edca0f7eaf10e6d50278a2b.png][]

核心： 先访问根结点，再访问左子树，最后访问右子树。

从根结点开始，首先访问根结点，再访问左子树，最后访问右子树，访问顺序：`EBG`  
从B 结点开始，首先访问B 结点，再访问左子树，最后访问右子树，访问顺序：`E BAD G`  
从G 结点开始，首先访问G 结点，再访问左子树，最后访问右子树，访问顺序：`E BAD GFH`  
从D 结点开始，首先访问D 结点，再访问左子树，最后访问右子树，访问顺序：`E BADC GFH`  
最终访问次序为：`E, B, A, D, C, G, F, H`

**递归版：**

class Solution { 
        public List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            preorderTraversal(root, list);
            return list;
        }
    
        public void preorderTraversal(TreeNode root, List<Integer> list) { 
            if (root == null) return;
            list.add(root.val);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }

**迭代版：**

class Solution { 
        public List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            while (!stack.isEmpty() || node != null) { 
                while (node != null) { 
                    list.add(node.val);
                    stack.push(node);
                    node = node.left;
                }
                node = stack.pop();
                node = node.right;
            }
            return list;
        }
    }

# 145. 二叉树的后序遍历 #

## 题目介绍 ##

给定一个二叉树，返回它的 **后序** 遍历。

**示例：**

输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [3,2,1]

进阶：递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![2723b0b59b98629860c33e78f47dade8.png][]

核心： 先访问左子树，再访问右子树，最后访问根结点。

从根结点开始，首先先访问左子树，再访问右子树，最后访问根结点，访问顺序：`BGE`

从B 结点开始，首先先访问左子树，再访问右子树，最后访问B 结点，访问顺序：`ADB G E`

从G 结点开始，首先先访问左子树，再访问右子树，最后访问G 结点，访问顺序：`ADB FHG E`

从D 结点开始，首先先访问左子树，再访问右子树，最后访问D 结点，访问顺序：`ACDB FHG E`

最终访问次序为：`A, C, D, B, F, H, G, E`

**递归版：**

class Solution { 
        public List<Integer> postorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            postorderTraversal(root, list);
            return list;
        }
    
        public void postorderTraversal(TreeNode root, List<Integer> list) { 
            if (root == null) return;
            postorderTraversal(root.left, list);
            postorderTraversal(root.right, list);
            list.add(root.val);
        }
    }

**迭代版：**

前序遍历：`根 左 右` ，后续遍历： `左 右 根`

我们只需要在前序遍历的基础上，修改遍历顺序为：`根 右 左`，然后对最终的结果进行反转即可。

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

# 226. 翻转二叉树 #

## 题目介绍 ##

翻转一棵二叉树。

**示例：**

**输入：**

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

**输出：**

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/invert-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

思路：翻转左子树后替换右子树，翻转右子树后替换左子树。

class Solution { 
        public TreeNode invertTree(TreeNode root) { 
            if (root == null) return null;
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }
    }

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

## 题目介绍 ##

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

百度百科中最近公共祖先的定义为：“对于有根树 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 均存在于给定的二叉树中。

**相同题目：**

*  #### [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先][Offer 68 - I.] ####
 *  #### [剑指 Offer 68 - II. 二叉树的最近公共祖先][Offer 68 - II.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

去以root为根节点的二叉树中查找p、q的最近公共祖先

*  如果p、q同时存在于这棵二叉树中，就能成功返回它们的最近公共祖先。
 *  如果p、q都不存在于这棵二叉树中，返回null，但是题目提示，p 和 q 均存在于给定的二叉树中，所以这种情况可以不用考虑。
 *  如果只有p存在于这棵二叉树中，返回p。
 *  如果只有q存在于这棵二叉树中，返回q。

完全版：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) return root;
            // 去以root.left 为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            if (left == null && right == null) return null;
            if (left != null && right == null) return left;
            if (left == null && right != null) return right;
            return null;
        }
    }

简化后：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) return root;
            // 去以root.left 为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            if (left != null && right == null) return left;
            if (left == null && right != null) return right;
            return null;
        }
    }

再简化：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) return root;
            // 去以root.left 为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            return (left != null) ? left : right;
        }
    }

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

## 题目介绍 ##

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

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

**示例 1：**

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

**示例 2：**

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

**示例 3：**

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

**示例 4：**

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

**提示：**

*  树中结点数在范围 \[0, 104\] 内
 *  \-1000 <= Node.val <= 1000

**相同题目：**

*  #### [449. 序列化和反序列化二叉搜索树][449.] ####
 *  #### [剑指 Offer 37. 序列化二叉树][Offer 37.] ####

**用到题目：**

*  #### [144. 二叉树的前序遍历][144.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

二叉树的序列化本质上是对其值进行编码，更重要的是对其结构进行编码。可以遍历树来完成上述任务。众所周知，我们一般有两个策略：广度优先搜索和深度优先搜索。

*  广度优先搜索可以按照层次的顺序从上到下遍历所有的节点
 *  深度优先搜索可以从一个根开始，一直延伸到某个叶，然后回到根，到达另一个分支。根据根节点、左节点和右节点之间的相对顺序，可以进一步将深度优先搜索策略区分为：
    
     *  前序遍历
     *  中序遍历
     *  后序遍历

这里，我们选择前序遍历的编码方式，实现对给定二叉树的编码。

![bb87736055b1338baa2fe629df109d49.png][]

即我们可以先前序遍历这颗二叉树，遇到空子树的时候序列化成 None（或者 null ），否则继续递归序列化。

那么我们如何反序列化呢？首先我们需要根据 , 把原先的序列分割开来得到先序遍历的元素列表，然后从左向右遍历这个序列：

*  如果当前的元素为 None，则当前为空树
 *  否则先解析这棵树的左子树，再解析它的右子树

public class Codec { 
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) { 
            StringBuilder sb = new StringBuilder();
            preorderTraversal(root, sb);
            return sb.toString();
        }
    
        private void preorderTraversal(TreeNode node, StringBuilder sb) { 
            if (node == null) { 
                sb.append("null").append(",");
            } else { 
                sb.append(node.val).append(",");
                preorderTraversal(node.left, sb);
                preorderTraversal(node.right, sb);
            }
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) { 
            if (data == null || data.length() == 0) return null;
            Queue<String> queue = new LinkedList<>();
            Collections.addAll(queue, data.split(","));
            return preorderBuilder(queue);
        }
    
        private TreeNode preorderBuilder(Queue<String> queue) { 
            if (queue.isEmpty()) return null;
            String current = queue.poll();
            if (current.equals("null")) return null;
            TreeNode root = new TreeNode(Integer.parseInt(current));
            root.left = preorderBuilder(queue);
            root.right = preorderBuilder(queue);
            return root;
        }
    }

# 572. 另一棵树的子树 #

## 题目介绍 ##

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

**示例 1：**

![9cedd0323f6fc39071d9b326333669f7.png][]

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

**示例 2：**

![8031bb2a15a9b622b07f336526721711.png][]

输入：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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/subtree-of-another-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public boolean isSubtree(TreeNode root, TreeNode subRoot) { 
            if (root == null || subRoot == null) return false;
            if (isSameTree(root, subRoot)) return true;
            return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
        }
    
        private boolean isSameTree(TreeNode t1, TreeNode t2) { 
            if (t1 == null && t2 == null) return true;
            if (t1 == null || t2 == null) return false;
            return (t1.val == t2.val) && isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
        }
    }

# 617. 合并二叉树 #

## 题目介绍 ##

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

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

**示例 1：**

**输入：**

Tree 1                     Tree 2                  
              1                         2                             
             / \                       / \                            
            3   2                     1   3                        
           /                           \   \                      
          5                             4   7

**输出：**

3
    	    / \
    	   4   5
    	  / \   \ 
    	 5   4   7

**注意：**

*  合并必须从两个树的根节点开始。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/merge-two-binary-trees  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

1、都是空树返回null

2、其中有一个空返回另一个树的根节点

3、都不空的话先把两棵树根节点值相加，然后递归合并左右子树(以第一棵树为合并后的树)

class Solution { 
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { 
            if (root1 == null && root2 == null) return null;
            if (root1 == null && root2 != null) return root2;
            if (root1 != null && root2 == null) return root1;
            root1.val += root2.val;
            root1.left = mergeTrees(root1.left, root2.left);
            root1.right = mergeTrees(root1.right, root2.right);
            return root1;
        }
    }

# 637. 二叉树的层平均值 #

## 题目介绍 ##

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

**示例 1：**

输入：
        3
       / \
      9  20
        /  \
       15   7
    输出：[3, 14.5, 11]
    解释：
    第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

**提示：**

*  节点值的范围在32位有符号整数范围内。

**用到题目：**

*  #### [102. 二叉树的层序遍历][102.] ####

## 题目实现 ##

class Solution { 
        public List<Double> averageOfLevels(TreeNode root) { 
            // 保存最终结果
            List<Double> levels = new ArrayList<>();
            // 进行临界判断
            if (root == null) return levels;
            // 创建一个队列
            Queue<TreeNode> queue = new LinkedList<>();
            // 加入指定结点
            queue.offer(root);
            // 循环弹出遍历
            while (!queue.isEmpty()) { 
                // 创建用于保存当前这一层的元素之和
                Double sum = 0.00D;
    
                int currSize = queue.size();
                for (int i = 0; i < currSize; i++) { 
                    // 从队列中弹出一个结点，保存当前结点的信息
                    TreeNode node = queue.poll();
                    sum += node.val;
                    // 判断当前结点还有没有左子结点，有的话入队
                    if (node.left != null) { 
                        queue.offer(node.left);
                    }
                    // 判断当前结点还有没有右子结点，有的话入队
                    if (node.right != null) { 
                        queue.offer(node.right);
                    }
                }
    
                levels.add(sum / currSize);
            }
            // 返回最终结果
            return levels;
        }
    }

# 654. 最大二叉树 #

## 题目介绍 ##

给定一个不含重复元素的整数数组 `nums` 。一个以此数组直接递归构建的 **最大二叉树** 定义如下：

1.  二叉树的根是数组 `nums` 中的最大元素。
2.  左子树是通过数组中 **最大值左边部分** 递归构造出的最大二叉树。
3.  右子树是通过数组中 **最大值右边部分** 递归构造出的最大二叉树。

返回有给定数组 `nums` 构建的 **最大二叉树** 。

**示例 1：**

![fa81aaa75d996c6cc5a5ba3642bf8cd0.png][]

输入：nums = [3,2,1,6,0,5]
    输出：[6,3,5,null,2,0,null,null,1]
    解释：递归调用如下所示：
    - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
        - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
            - 空数组，无子节点。
            - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
                - 空数组，无子节点。
                - 只有一个元素，所以子节点是一个值为 1 的节点。
        - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
            - 只有一个元素，所以子节点是一个值为 0 的节点。
            - 空数组，无子节点。

**示例 2：**

![33c86363fd250605f729becbed6b4960.png][]

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

**提示：**

*  1 <= nums.length <= 1000
 *  0 <= nums\[i\] <= 1000
 *  nums 中的所有整数 互不相同

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

我们首先构造出一个函数：`findRoot(int[] nums, int left, int right)`，它的作用：找出 \[ left , right ) 范围的根节点，这样就能把一个数组分割成两部分，左边是比根节点小的，右边是比根节点大的，通过递归调用，最终构造出一棵最大二叉树。

class Solution { 
        public TreeNode constructMaximumBinaryTree(int[] nums) { 
            if (nums == null || nums.length == 0) return null;
            return findRoot(nums, 0, nums.length);
        }
    
        // 找出 [ left , right ) 范围的根节点
        public TreeNode findRoot(int[] nums, int left, int right) { 
            if (left == right) return null;
            int maxIndex = left;
            for (int i = left + 1; i < right; i++) { 
                if (nums[i] > nums[maxIndex]) { 
                    maxIndex = i;
                }
            }
            TreeNode root = new TreeNode(nums[maxIndex]);
            root.left = findRoot(nums, left, maxIndex);
            root.right = findRoot(nums, maxIndex + 1, right);
            return root;
        }
    }

**题目变种：返回一个数组，里面存着每个节点的父索引，如果没有父节点，就存入 `-1`，传入的 `nums` 中的所有整数互不相同。**

![7d79fd59387f0daed264af3b1b9f2404.png][]

要想找某个元素的父节点，其实就是找该元素的离他最近出现的最大值。分为以下三种情况：

*  我们看上图原数组中的元素3，离他最近的最大值，只能往数组右边看，也就是6。
 *  我们看上图原数组中的元素5，离他最近的最大值，只能往数组左边看，也就是6。
 *  我们看上图原数组中的元素1，向左离他最近的最大值为2，向右离他最近的最大值为6，最接近的是2。

我们可以使用 **栈** 这种结构，只需要遍历一次 **原数组** ，就能知道每个元素的父节点是谁，具体怎么做，请看以下操作。

![64770081635aca523836beaa1918e7e3.png][]

*  定义一个数组，用于存放左边第一个比他大的值的索引，然后全部初始化为 -1
 *  定义一个数组，用于存放右边第一个比他大的值的索引，然后全部初始化为 -1
 *  定义一个栈

以上结构定义好了之后，我们 **从左向右** 依次遍历原数组 `nums`。

当前指向的元素是**3**，直接加入栈中，此时栈为空，然后指针后移。

// 先写 1. 将元素当前的索引加入栈
    stack.push(i);

![1a747b987b2dc6b47a2b86af65d94a16.png][]

当前指向的元素是 **2**，直接加入栈中，此时栈不空，则元素 **2** 左边的第一个比他大的数就是元素 **3**，然后指针后移。

// 再写 2. 元素左边首个最大值索引
    if (!stack.isEmpty()) { 
        lis[i] = stack.peek();
    }

![7d7f462b759d620a78a97698aacf310f.png][]

当前指向的元素是 **1**，直接加入栈中，此时栈不空，则元素 **1** 左边的第一个比他大的数就是元素 **2**，然后指针后移。

![47359de1df02eb2bc0ac3cea868d22f6.png][]

当前指向的元素是 **6**，此时栈不空，并且栈顶元素 **1** **小于** 元素 **6** ，则栈顶右边第一个比他大的数就是元素 **6**，弹出栈顶元素，指针不动。

// 最后 3. 元素右边首个最大值索引
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { 
        ris[stack.pop()] = i;
    }

![14a395189241b09e36afcee9c5fac1b2.png][]

当前指向的元素是 **6**，此时栈不空，并且栈顶元素 **2** **小于** 元素 **6** ，则栈顶右边第一个比他大的数就是元素 **6**，弹出栈顶元素，指针不动。

![c34016c394506f58472fceddf088f752.png][]

当前指向的元素是 **6**，此时栈不空，并且栈顶元素 **3** **小于** 元素 **6** ，则栈顶右边第一个比他大的数就是元素 **6**，弹出栈顶元素，指针不动。

![2295bad53db4df83bbd3ad6f944ac99a.png][]

当前指向的元素是 **6**，此时栈为空，将元素 **6** 直接加入栈中，然后指针后移。按照上述的模式进行判断，直到数组元素遍历完毕即结束。

![feef80f65b060ab347bbc7e91a16840c.png][]

public int[] parseParentIndexs(int[] nums) { 
        if (nums == null || nums.length == 0) return null;
        // 定义一个数组，用于存放左边第一个比他大的值的索引，然后全部初始化为 -1
        int[] lis = new int[nums.length];
        Arrays.fill(lis, -1);
        // 定义一个数组，用于存放右边第一个比他大的值的索引，然后全部初始化为 -1
        int[] ris = new int[nums.length];
        Arrays.fill(ris, -1);
        // 定义一个栈
        Stack<Integer> stack = new Stack<>();
        // 遍历 nums 数组的所有元素
        for (int i = 0; i < nums.length; i++) { 
            // 最后 3. 元素右边首个最大值索引
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { 
                ris[stack.pop()] = i;
            }
            // 再写 2. 元素左边首个最大值索引
            if (!stack.isEmpty()) { 
                lis[i] = stack.peek();
            }
            // 先写 1. 将元素当前的索引加入栈
            stack.push(i);
        }
        // 组装 nums 所有元素根节点
        int[] pis = new int[nums.length];
        for (int i = 0; i < pis.length; i++) { 
            // 最大二叉树根节点
            if (lis[i] == -1 && ris[i] == -1) { 
                pis[i] = -1;
                continue;
            }
            // 不是根节点的节点
            if (lis[i] == -1) { 
                pis[i] = ris[i];
            } else if (ris[i] == -1) { 
                pis[i] = lis[i];
            } else if (nums[lis[i]] < nums[ris[i]]) { 
                pis[i] = lis[i];
            } else { 
                pis[i] = ris[i];
            }
        }
        return pis;
    }

# 94. 二叉树的中序遍历 #

## 题目介绍 ##

给定一个二叉树的根节点 `root` ，返回它的 `中序` 遍历。

**示例 1：**

![38a932444dea99069c7c58e0329f32b8.png][]

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

**示例 2：**

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

**示例 3：**

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

**示例 4：**

![6ea479bf22ac3b2af3ea885e0e4472fc.png][]

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

**示例 5：**

![70abacc695b8856b33c9f450080f0978.png][]

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

**提示：**

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![c0bd728751d82bf092b85615ce591eda.png][]

核心： 先访问左子树，再访问根结点，最后访问右子树。

从根结点开始，首先访问左子树，再访问根结点，最后访问右子树，访问顺序：`BEG`

从`B` 结点开始，首先访问左子树，再访问`B` 结点，最后访问右子树，访问顺序：`ABD E G`

从`G` 结点开始，首先访问左子树，再访问`G` 结点，最后访问右子树，访问顺序：`ABD E FGH`

从`D` 结点开始，首先访问左子树，再访问`D` 结点，不用输出右子树，访问顺序：`ABCD E FGH`

最终访问次序为：`A, B, C, D, E, F, G, H`

**递归版：**

class Solution { 
        public List<Integer> inorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            inorderTraversal(root, list);
            return list;
        }
    
        public void inorderTraversal(TreeNode root, List<Integer> list) { 
            if (root == null) return;
            inorderTraversal(root.left, list);
            list.add(root.val);
            inorderTraversal(root.right, list);
        }
    }

**迭代版：**

class Solution { 
        public List<Integer> inorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            while (!stack.isEmpty() || node != null) { 
                while (node != null) { 
                    stack.push(node);
                    node = node.left;
                }
                node = stack.pop();
                list.add(node.val);
                node = node.right;
            }
            return list;
        }
    }

# 965. 单值二叉树 #

## 题目介绍 ##

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

**示例 1：**

![92b02364218654fde02d2d628de2e4a3.png][]

输入：[1,1,1,1,1,null,1]
    输出：true

**示例 2：**

![870387e2a376dfc45ebbab15cd560fe3.png][]

输入：[2,2,2,5,2]
    输出：false

**提示：**

*  给定树的节点数范围是 \[1, 100\]。
 *  每个节点的值都是整数，范围为 \[0, 99\] 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/univalued-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public boolean isUnivalTree(TreeNode root) { 
            if (root == null) return true;
            if (root.left != null && root.left.val != root.val) return false;
            if (root.right != null && root.right.val != root.val) return false;
            return isUnivalTree(root.left) && isUnivalTree(root.right);
        }
    }

# 98. 验证二叉搜索树 #

## 题目介绍 ##

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

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

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

**示例 1：**

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

**示例 2：**

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

**相同题目：**

*  #### [面试题 04.05. 合法二叉搜索树][04.05.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/validate-binary-search-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

我们可以知道二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是。

可能由读者不知道中序遍历是什么，我们这里简单提及一下，中序遍历是二叉树的一种遍历方式，它先遍历左子树，再遍历根节点，最后遍历右子树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。

class Solution { 
        private TreeNode prev;
    
        public boolean isValidBST(TreeNode root) { 
            return inorderTraversalValidBST(root);
        }
    
        public boolean inorderTraversalValidBST(TreeNode node) { 
            if (node == null) return true;
            boolean left = inorderTraversalValidBST(node.left);
            if (prev != null && prev.val >= node.val) return false;
            prev = node;
            boolean right = inorderTraversalValidBST(node.right);
            return left && right;
        }
    }

# 99. 恢复二叉搜索树 #

## 题目介绍 ##

给你二叉搜索树的根节点 `root` ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 `O(n)` 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

**示例 1：**

![6261d32b006942fcc16839990a9b6ddd.png][]

输入：root = [1,3,null,null,2]
    输出：[3,1,null,null,2]
    解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

**示例 2：**

![c4024eb8c031008a7006052d649dbe68.png][]

输入：root = [3,1,4,null,null,2]
    输出：[2,1,4,null,null,3]
    解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

**提示：**

*  树上节点的数目在范围 \[2, 1000\] 内
 *  \-231 <= Node.val <= 231 \- 1

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/recover-binary-search-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![e2a4a82231ff70849e16b574d0f5d02a.png][]

使用中序遍历二叉搜索树，我们将得到一个升序的数组，这就是求解这道题的关键所在。

而一旦出现错误的节点，就会导致，使用中序遍历的时候，不是升序数组，有两种情况：

![e18dcba771d3710f8c5fdecd8859e096.png][]

完整版：

class Solution { 
        private TreeNode prev;      // 上次遍历的节点
        private TreeNode first;     // 第一个错误节点
        private TreeNode second;    // 第二个错误节点
    
        public void recoverTree(TreeNode root) { 
            // 查找出错位置
            inorderTraversal(root);
            // 交换出错位置
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    
        public void inorderTraversal(TreeNode node) { 
            if (node == null) return;
            inorderTraversal(node.left);
            if (prev != null && prev.val > node.val) { 
                // 第1个错误节点：第一个逆序对中较大的那个节点
                if (first == null) { 
                    first = prev;
                }
                // 第2个错误节点：最后一个逆序对中较小的那个节点
                second = node;
            }
            prev = node;
            inorderTraversal(node.right);
        }
    }

优化版：

class Solution { 
        private TreeNode prev;      // 上次遍历的节点
        private TreeNode first;     // 第一个错误节点
        private TreeNode second;    // 第二个错误节点
    
        public void recoverTree(TreeNode root) { 
            // 查找出错位置
            inorderTraversal(root);
            // 交换出错位置
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    
        public void inorderTraversal(TreeNode node) { 
            if (node == null) return;
            inorderTraversal(node.left);
            if (prev != null && prev.val > node.val) { 
                // 第2个错误节点：最后一个逆序对中较小的那个节点
                second = node;
                // 第1个错误节点：第一个逆序对中较大的那个节点
                if (first != null) return;
                first = prev;
            }
            prev = node;
            inorderTraversal(node.right);
        }
    }

# 剑指 Offer 07. 重建二叉树 #

## 题目介绍 ##

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

**示例 1：**

![ff3a53d9fd4cda56349a97000cc0d833.png][]

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    Output: [3,9,20,null,null,15,7]

**示例 2：**

Input: preorder = [-1], inorder = [-1]
    Output: [-1]

**提示：**

*  0 <= 节点个数 <= 5000

**相同题目：**

*  #### [105. 从前序与中序遍历序列构造二叉树][105.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

## 题目介绍 ##

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

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

1
       / \
      2   2
     / \ / \
    3  4 4  3

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

1
       / \
      2   2
       \   \
       3    3

**示例 1：**

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

**示例 2：**

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

**限制：**

*  0 <= 节点个数 <= 1000

**相同题目：**

*  #### [101. 对称二叉树][101.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![9c67aacf604acf4fd7900ac9cdab5ddc.png][]

class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            return root == null ? true : symmetric(root.left, root.right);
        }
    
        private boolean symmetric(TreeNode L, TreeNode R) { 
            if (L == null && R == null) return true;
            if (L == null || R == null) return false;
            return (L.val == R.val) && symmetric(L.left, R.right) && symmetric(L.right, R.left);
        }
    }

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

## 题目介绍 ##

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

**例如：**

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

3
       / \
      9  20
        /  \
       15   7

**返回：**

[3,9,20,15,7]

**提示：**

*  节点总数 <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int[] levelOrder(TreeNode root) { 
            if (root == null) return new int[0];
            ArrayList<Integer> list = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) { 
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) { 
                res[i] = list.get(i);
            }
            return res;
        }
    }
    ```# 剑指 Offer 32 - II. 从上到下打印二叉树 II
    
    ## 题目介绍
    
    从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
    
    **例如：**
    
    给定二叉树: [3,9,20,null,null,15,7],

/  
9 20  
/  
15 7

返回其层次遍历结果：

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

**提示：**
    
    - 节点总数 <= 1000
    
    **相同题目：**
    
    - #### [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    
    ## 题目实现
    
    ```java
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> levels = new ArrayList<>();
            if (root == null) return levels;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> level = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    level.add(node.val);
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                }
                levels.add(level);
            }
            return levels;
        }
    }
    ```# 剑指 Offer 32 - III. 从上到下打印二叉树 III
    
    ## 题目介绍
    
    请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
    
    **例如：**
    
    给定二叉树: [3,9,20,null,null,15,7],

/  
9 20  
/  
15 7

返回其层次遍历结果：

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

**提示：**
    
    - 节点总数 <= 1000
    
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    
    ## 题目实现
    
    ```java
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> levels = new ArrayList<>();
            if (root == null) return levels;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> level = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    level.add(node.val);
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                }
                if (levels.size() % 2 == 1) {
                    Collections.reverse(level);
                }
                levels.add(level);
            }
            return levels;
        }
    }

# 剑指 Offer 33. 二叉搜索树的后序遍历序列 #

## 题目介绍 ##

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

5
        / \
       2   6
      / \
     1   3

**示例 1：**

输入: [1,6,3,2,5]
    输出: false

**示例 2：**

输入: [1,3,2,6,5]
    输出: true

**提示：**

*  数组长度 <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public boolean verifyPostorder(int[] postorder) { 
            return helper(postorder, 0, postorder.length - 1);
        }
    
        private boolean helper(int[] postorder, int left, int right) { 
            //终止的条件
            if (left >= right) return true;
            //找到根节点
            int root = postorder[right];
            //判断左子树
            int i = left;
            while (postorder[i] < root) { 
                i++;
            }
            //判断右子树
            for (int j = i; j < right; j++) { 
                if (postorder[j] < root) { 
                    return false;
                }
            }
            //递归判断
            return helper(postorder, left, i - 1) && helper(postorder, i, right - 1);
        }
    }
    ```# 剑指 Offer 34. 二叉树中和为某一值的路径
    
    ## 题目介绍
    
    输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
    
    **示例：**
    
    给定如下二叉树，以及目标和 target = 22，
    
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1
    **返回：**

\[  
\[5,4,11,2\],  
\[5,8,4,5\]  
\]

**提示：**
    
    - 节点总数 <= 10000
    
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    
    ## 题目实现
    
    ```java
    import java.util.ArrayList;
    import java.util.List;
    
    class Solution {
        private List<List<Integer>> result = new ArrayList<>();
        private List<Integer> list = new ArrayList<>();
    
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            dfs(root, target);
            return result;
        }
    
        private void dfs(TreeNode node, int target) {
            //无效节点
            if (node == null) return;
            //添加节点
            list.add(node.val);
            target -= node.val;
            //叶子节点
            if (node.left == null && node.right == null && target == 0) {
                result.add(new ArrayList<>(list));
            }
            //深度优先
            dfs(node.left, target);
            dfs(node.right, target);
            //移除节点
            list.remove(list.size() - 1);
        }
    }
    ```# 剑指 Offer 36. 二叉搜索树与双向链表
    
    ## 题目介绍
    
    输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
    
    为了让您更好地理解问题，以下面的二叉搜索树为例：
    
     ![](https://gitee.com/caochenlei/blog-images/raw/master/20211006182807.png)
    
    我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
    
    下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
    
    ![](https://gitee.com/caochenlei/blog-images/raw/master/20211006182822.png)
    
    特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
    
    **相同题目：**
    
    - #### [426. 将二叉搜索树转化为排序的双向链表](https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/)
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    
    ## 题目实现
    
    ![](https://gitee.com/caochenlei/blog-images/raw/master/20211006183422.png)
    
    ![](https://gitee.com/caochenlei/blog-images/raw/master/20211006183439.png)
    
    ![](https://gitee.com/caochenlei/blog-images/raw/master/20211006183521.png)
    
    ![](https://gitee.com/caochenlei/blog-images/raw/master/20211006183607.png)
    
    ![](https://gitee.com/caochenlei/blog-images/raw/master/20211006183636.png)
    
    ```java
    class Solution {
        private Node head, pre;
    
        public Node treeToDoublyList(Node root) {
            if (root == null) return null;
            dfs(root);
            head.left = pre;
            pre.right = head;
            return head;
        }
    
        private void dfs(Node cur) {
            if (cur == null) return;
            dfs(cur.left);
            if (pre == null) {
                head = cur;
                pre = cur;
            } else {
                pre.right = cur;
                cur.left = pre;
                pre = cur;
            }
            dfs(cur.right);
        }
    }

# 剑指 Offer 37. 序列化二叉树 #

## 题目介绍 ##

请实现两个函数，分别用来序列化和反序列化二叉树。

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

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

**示例：**

![7ed5c6427508f35d5430f85c48d2045a.png][]

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

相同题目：

*  #### [297. 二叉树的序列化与反序列化][297.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Codec { 
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) { 
            StringBuilder sb = new StringBuilder();
            preorderTraversal(root, sb);
            return sb.toString();
        }
    
        private void preorderTraversal(TreeNode node, StringBuilder sb) { 
            if (node == null) { 
                sb.append("null").append(",");
            } else { 
                sb.append(node.val).append(",");
                preorderTraversal(node.left, sb);
                preorderTraversal(node.right, sb);
            }
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) { 
            if (data == null || data.length() == 0) return null;
            Queue<String> queue = new LinkedList<>();
            Collections.addAll(queue, data.split(","));
            return preorderBuilder(queue);
        }
    
        private TreeNode preorderBuilder(Queue<String> queue) { 
            if (queue.isEmpty()) return null;
            String current = queue.poll();
            if (current.equals("null")) return null;
            TreeNode node = new TreeNode(Integer.parseInt(current));
            node.left = preorderBuilder(queue);
            node.right = preorderBuilder(queue);
            return node;
        }
    }

[9fa10c77dbb951f3e6d1b80b115dc2ff.png]: /images/20221014/348e97bf9f5043b39f85a9134d6d5b41.png
[1c681f82a045bac20a1d156bb356dc7f.png]: /images/20221014/d25e643b14ac4c2f86158006d061deb0.png
[981bac584ca594d969b56fadca15237a.png]: /images/20221014/f26290b99c614231bd7c7504a2c4593d.png
[Offer 28.]: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
[e672f9e1b99f1aede8a6aed942397ec6.png]: /images/20221014/d087cd4b22e34c569982c8d7c7cdbfa3.png
[9c67aacf604acf4fd7900ac9cdab5ddc.png]: /images/20221014/4675730672af4c4fbfa28f72f30e066b.png
[66f92634240a8c3b4fd6505b82014f82.png]: /images/20221014/9e35cc8790274e4f89154a456e6a35db.png
[3a55af3a2e181a48953a76f95a398ab9.png]: /images/20221014/c3fdd41a2d5642e788622a31fee2359a.png
[0b20a5287ecd8a235ea5f09793e7ed0a.png]: /images/20221014/ade9dbca607e4dc8a7dcfc01d753234c.png
[Offer 55 - I.]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
[ff3a53d9fd4cda56349a97000cc0d833.png]: /images/20221014/b5c8b57da7f948ac96adb53ba9c4bce0.png
[Offer 07.]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[5d18a5d96c15f7f06b7833b3b0ccf6ad.png]: /images/20221014/1054c299b471466b8293189cf57afb81.png
[0cd152e25159d8276429417d471a1a8d.png]: /images/20221014/1cb9b4c64c334f94a571f1d60fbaa8d1.png
[Offer 55 - II.]: https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
[f7e8ab02cb555ef1017905de2c9c35a7.png]: /images/20221014/066e064135594724abaffd74f94d4cca.png
[54cda28cb2cfac46c1e39ba0cce77eff.png]: /images/20221014/9174fadb3e8145ab8fb9ecb8eb87cc79.png
[8ea29f3c8e411003619e1a3a1ad7357d.png]: /images/20221014/dbd5ed0a2af5489bbeb95d2213a756aa.png
[52c3fd6da2b3e199da484e8afcaad142.png]: /images/20221014/e690dfa3fa5d4f6bba355a99613216ca.png
[8e6c4c32c18f8604e73e0c5a538b6a57.png]: /images/20221014/e874fa80f2e14b1b98d0bd7b8bce573f.png
[433a9a16d4435abcbf764e0ac7b099bd.png]: /images/20221014/f1959b05ac004138bb55babc48b06418.png
[e22679e4c0122466be5a1bac20ee5fd9.png]: /images/20221014/05151a965135438ba929827cdfb97f73.png
[e9c0faa94c3e835387b847ce55f9f0e9.png]: /images/20221014/0002fed86ab8431ea7d157f366d28fca.png
[a331ea6a6edca0f7eaf10e6d50278a2b.png]: /images/20221014/7571dfe7144b45aa852b42eb5dc24df8.png
[2723b0b59b98629860c33e78f47dade8.png]: /images/20221014/0813765e6f5342f48cb21f8603b54b6b.png
[Offer 68 - I.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Offer 68 - II.]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[449.]: https://leetcode-cn.com/problems/serialize-and-deserialize-bst/
[Offer 37.]: https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
[144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[bb87736055b1338baa2fe629df109d49.png]: /images/20221014/9b1c95da77a941d487b21b08af6ff05e.png
[9cedd0323f6fc39071d9b326333669f7.png]: /images/20221014/4c9c16a61442447b82cc9e027e3d2825.png
[8031bb2a15a9b622b07f336526721711.png]: /images/20221014/062763978fd646dc81e24a8f34abe76b.png
[102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[fa81aaa75d996c6cc5a5ba3642bf8cd0.png]: /images/20221014/b575f50249e9493489659ad01f2b98b7.png
[33c86363fd250605f729becbed6b4960.png]: /images/20221014/09b0b55f222746ce8a2b36118f3b7d36.png
[7d79fd59387f0daed264af3b1b9f2404.png]: /images/20221014/b53e6990d81a411ba578eb8ae16b7492.png
[64770081635aca523836beaa1918e7e3.png]: /images/20221014/4b497678da944f5ab25f228888fb6a4c.png
[1a747b987b2dc6b47a2b86af65d94a16.png]: /images/20221014/a4f98c59ed5849a4b3a200802fcc7349.png
[7d7f462b759d620a78a97698aacf310f.png]: /images/20221014/cdb27098e2b146b294e448a748e86019.png
[47359de1df02eb2bc0ac3cea868d22f6.png]: /images/20221014/e3a17b66cbd54651a2f7315ebbe38983.png
[14a395189241b09e36afcee9c5fac1b2.png]: /images/20221014/f27ea86834bf4b65bdea10b6dda4b465.png
[c34016c394506f58472fceddf088f752.png]: /images/20221014/811ca6e5909a474398a607fc11bef408.png
[2295bad53db4df83bbd3ad6f944ac99a.png]: /images/20221014/2639afce052f45979d705587ae4fee2f.png
[feef80f65b060ab347bbc7e91a16840c.png]: /images/20221014/00dcc218d6b04566a964df4371494b81.png
[38a932444dea99069c7c58e0329f32b8.png]: /images/20221014/da84e85135a249fba542d7f85ba3d02f.png
[6ea479bf22ac3b2af3ea885e0e4472fc.png]: /images/20221014/1be4d9b9e0254381b161b1210d8dd239.png
[70abacc695b8856b33c9f450080f0978.png]: /images/20221014/eb646d9687ec496282af30bde72d2a7c.png
[c0bd728751d82bf092b85615ce591eda.png]: /images/20221014/c080718f780b4b08a66535966f508be1.png
[92b02364218654fde02d2d628de2e4a3.png]: /images/20221014/af65cf49708742608445df5235cffd12.png
[870387e2a376dfc45ebbab15cd560fe3.png]: /images/20221014/1e8f52d20664439e9117ac7740cc39cb.png
[04.05.]: https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/
[6261d32b006942fcc16839990a9b6ddd.png]: /images/20221014/dcb0d21fbbd04a76896ee54bd3d65681.png
[c4024eb8c031008a7006052d649dbe68.png]: /images/20221014/1eb52b18796a40589674c16bb17d572d.png
[e2a4a82231ff70849e16b574d0f5d02a.png]: /images/20221014/7620966d0b194eabbc6fa3296dfb4f69.png
[e18dcba771d3710f8c5fdecd8859e096.png]: /images/20221014/5f230f47ccba4245a13418d2d7ff4050.png
[105.]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[101.]: https://leetcode-cn.com/problems/symmetric-tree/
[7ed5c6427508f35d5430f85c48d2045a.png]: /images/20221014/e618d691d7c1459d99d427a5b34a0f1e.png
[297.]: https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/