重建二叉树
【题目】：
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树，并返回重建后二叉树的根节点。
假设两个遍历的结果中没有重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：3
/ \
9 20
/ \
15 7
【解题思路】：
- 从前序遍历中找到第一个结果作为根节点；
- 在中序遍历中找到这个值，则这个值左边的值是左子节点；右边则是右子节点；
- 利用递归，采用同样的方法重构二叉树。
# Define functions for binary tree
class TreeNode(object):def __init__(self, val):self.val = valself.left = Noneself.right = None# preOrder function
def pro_order(root):if not root:returnprint(root.val, end="->")pro_order(root.left)pro_order(root.right)# inOrder function
def in_order(root):if not root:returnin_order(root.left)print(root.val, end='->')in_order(root.right)# Construct the binary tree
def construct_binary_tree(pro_order, in_order):if not pro_order or not in_order or len(pro_order) != len(in_order):returndef construct(pro_order, in_order):if not pro_order:return None# build root noderoot = TreeNode(pro_order[0])# find root node in inorderfor i in range(len(in_order)):if in_order[i] == root.val:break# build left treeroot.left = construct(pro_order[1: len(in_order[:i]) + 1], in_order[:i])# build right treeroot.right = construct(pro_order[i + 1:], in_order[i + 1:])return rootreturn construct(pro_order, in_order)# test
pre = [1, 2, 4, 7, 3, 5, 6, 8]
ino = [4, 7, 2, 1, 5, 3, 8, 6]
root = construct_binary_tree(pre, ino)
print("PreOrder:")
pro_order(root)
print("None\nInOrder:")
in_order(root)
print("None")运行结果：
示例代码2：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def buildTree(self, preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: TreeNode"""if (not preorder) and (not inorder) and (len(preorder) == len(inorder)):return Nonenode = TreeNode(preorder[0])index = inorder.index(preorder[0])left_pre = preorder[1:index+1]left_in = inorder[:index]right_pre = preorder[index+1:]right_in = inorder[index+1:]node.left = self.buildTree(left_pre, left_in)node.right = self.buildTree(right_pre, right_in)return node
