重建二叉树（Python and C++解法）
2021-05-06 13:28
标签：dtree roo for == style int col tps dex 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 3 来源：力扣（LeetCode） 3 9 【 20 15 7 】 根节点 左子树 右子树 9 3 【 15 20 7 】 左子树 根节点 右子树 根据前序遍历，可以确定根节点；根据中序遍历，可以确定左子树节点和右子树节点，同时可以确定子树节点的前序遍历和中序遍历结果，因此根据节点使用递归方法建立子树。 重建二叉树（Python and C++解法） 标签：dtree roo for == style int col tps dex 原文地址：https://www.cnblogs.com/kongzimengzixiaozhuzi/p/13187993.html题目：
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
/ \
9 20
/ \
15 7
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof思路：
Python解法：
1 # 定义二叉树
2 class TreeNode:
3 def __init__(self, x): # self相当于类的实例
4 self.val = x
5 self.left = None
6 self.right = None
7
8
9 class Solution:
10 def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
11 if not preorder or not inorder or len(preorder) != len(inorder): # 考虑异常条件
12 return None
13 root = preorder[0]
14 rootNode = TreeNode(root) # 建立根节点
15 pos = inorder.index(root) # 确定根节点在中序遍历中的索引位置
16
17 preorderLeft = preorder[1:pos+1] # 前序遍历的左子树
18 preorderRight = preorder[pos+1:] # 前序遍历的右子树
19
20 inorderLeft = inorder[:pos] # 中序遍历的左子树
21 inorderRight = inorder[pos+1:] # 中序遍历的右子树
22
23 leftNode = self.buildTree(preorderLeft, inorderLeft) # 递归到左子树的根节点
24 rightNode = self.buildTree(preorderRight, inorderRight) # 递归到右子树的根节点
25 rootNode.left = leftNode
26 rootNode.right = rightNode
27 return rootNode
C++解法：
1 struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6 };
7
8 class Solution {
9 public:
10 TreeNode* buildTree(vectorint>& preorder, vectorint>& inorder) {
11 if (preorder.size() == 0 || inorder.size() == 0 || preorder.size() != inorder.size()) // 考虑异常情况
12 return NULL;
13
14 int root = preorder[0];
15 TreeNode *rootNode = new TreeNode(root); // 建立根节点时，一定要用new!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
16 int pos; // 根节点在中序遍历中的下标
17 for (int i = 0; i )
18 if (inorder[i] == root) {
19 pos = i;
20 break;
21 }
22
23 vectorint> preorderLeft; // 前序遍历的左子树
24 vectorint> preorderRight; // 前序遍历的右子树
25 for (int i = 1; i )
26 preorderLeft.push_back(preorder[i]);
27 for (int i = pos + 1; i )
28 preorderRight.push_back(preorder[i]);
29
30 vectorint> inorderLeft; // 中序遍历的左子树
31 vectorint> inorderRight; // 中序遍历的右子树
32 for (int i = 0; i )
33 inorderLeft.push_back(inorder[i]);
34 for (int i = pos + 1; i )
35 inorderRight.push_back(inorder[i]);
36
37 TreeNode *leftNode = buildTree(preorderLeft, inorderLeft); // 递归到左子树的根节点
38 TreeNode *rightNode = buildTree(preorderRight, inorderRight); // 递归到右子树的根节点
39 rootNode->left = leftNode;
40 rootNode->right = rightNode;
41
42 return rootNode;
43 }
44 };