第 7 题：重建二叉树（递归）
同 LeetCode 第 105 题，传送门：从前序与中序遍历序列构造二叉树。
传送门：AcWing：重建二叉树，牛客网 online judge 地址。
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意:
- 二叉树中每个节点的值都互不相同；
- 输入的前序遍历和中序遍历一定合法；
样例：
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]返回：
[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：3 / \ 9 20 / \ 15 7
分析：
- 画图是解决这一类问题的关键，千万不要犯懒，拿出纸和笔，动手操作一下，往往思路就很清晰了；
- 用类似二叉树插入节点的方式建立二叉树，即使用递归函数，返回新创建二叉树根节点的方式，将新的二叉树的根结点挂接到原来的二叉树的左右结点中；
- 前序遍历的第 1 个元素就是二叉树的根结点。根据这一点，不难写出递归函数的代码。注意这是以“输入的前序遍历和中序遍历的结果中都不含重复的数字”为前提的。
《剑指 Offer （第 2 版）》第 7 题：重建二叉树-3
《剑指 Offer （第 2 版）》第 7 题：重建二叉树-4
思路：递归重建。二叉树的 DFS 有如下三种遍历方式：
- 前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。
- 中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。
- 后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。
本题为前序遍历和中序遍历，最少需要两种遍历方式，才能重建二叉树。
关键：前序遍历数组的第 个数（索引为
）的数一定是二叉树的根结点，于是可以在中序遍历中找这个根结点的索引，然后把“前序遍历数组”和“中序遍历数组”分为两个部分，就分别对应二叉树的左子树和右子树，分别递归完成就可以了。
《剑指 Offer （第 2 版）》第 7 题：重建二叉树-1
《剑指 Offer （第 2 版）》第 7 题：重建二叉树-4
注意：1、编写递归方法的时候，先写特殊情况；
2、索引是多少不好判断的时候，干脆就用一个具体的例子，就比如我上面画的这个图，把具体的数换成我们使用的变量，这样思考的难度会降低，而且还不容易出错。
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
返回构造的 TreeNode 根结点
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
# 在编码过程中，一定要保证 len(pre) == len(tin)，否则逻辑一定不正确
if len(preorder) == 0:
return None
if len(preorder) == 1:
# 这里要返回结点，而不是返回具体的数
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
# 直接得到在中序遍历中的位置，下面算好偏移量就好了，如果容易算错，记得拿具体例子
pos = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:pos + 1], inorder[:pos])
root.right = self.buildTree(preorder[pos + 1:], inorder[pos + 1:])
return root
Java 代码：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
return root;
}
/**
* 根据前序遍历数组的 [preL, preR] 和 中序遍历数组的 [inL, inR] 重新组建二叉树
*
* @param pre 前序遍历数组
* @param preL 前序遍历数组的区间左端点
* @param preR 前序遍历数组的区间右端点
* @param in 中序遍历数组
* @param inL 中序遍历数组的区间左端点
* @param inR 中序遍历数组的区间右端点
* @return 构建的新二叉树的根结点
*/
private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
if (preL > preR || inL > inR) {
return null;
}
// 构建的新二叉树的根结点一定是前序遍历数组的第 1 个元素
TreeNode root = new TreeNode(pre[preL]);
// 从中序遍历的左区间端点开始找，找到和前序遍历数组的第 1 个元素的值相等的节点
int i = inL;
while (in[i] != pre[preL] && i <= inR) {
i++;
}
// 在中序遍历数组中遍历了几个元素： i - inL
// 接下来就是递归调用，关键的地方在于找前序遍历数组和中序遍历数组对应的区间的端点
root.left = reConstructBinaryTree(pre, preL + 1, preL + (i - inL), in, inL, i - 1);
root.right = reConstructBinaryTree(pre, preL + (i - inL) + 1, preR, in, i + 1, inR);
return root;
}
}
类似问题：LeetCode 第 106 题。
LeetCode 第 106 题：从中序与后序遍历序列构造二叉树
传送门：106. 从中序与后序遍历序列构造二叉树。
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如，给出
中序遍历 inorder =
[9,3,15,20,7]
后序遍历 postorder =[9,15,7,20,3]返回如下的二叉树：
3 / \ 9 20 / \ 15 7
思路：二叉树的问题，在纸上写写画画更形象。
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
assert len(inorder) == len(postorder)
if len(inorder) == 0:
return None
if len(inorder) == 1:
# 这里要返回结点，而不是返回具体的数
return TreeNode(inorder[0])
# 最后一个结点是根结点
root = TreeNode(postorder[-1])
pos = inorder.index(postorder[-1])
root.left = self.buildTree(inorder[:pos], postorder[:pos])
root.right = self.buildTree(inorder[pos + 1:], postorder[pos:-1])
return root
# 用于验证的方法
def validate(node):
if node is None:
return
validate(node.left)
print(node.val, end=' ')
validate(node.right)
if __name__ == '__main__':
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
solution = Solution()
root = solution.buildTree(inorder, postorder)
validate(root)
