题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3 / \ 9 20 / \ 15 7
解题
方法一：递归（4个参数）
我们只需要在前序遍历中找到，左子树，在中序遍历中，找到左子树。同理，找到右子树。就能利用递归的方式了去完成了。
由于树中没有重复的元素，于是元素的值和索引是一一对应的，这样的树才是唯一确定的。
pIndex是通过，遍历 中序遍历的结果，哈希表中，值对应索引。这样能通过根的值，来找到在中序遍历中的索引。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int): if preorder_left > preorder_right: return None # 前序遍历中的第一个节点就是根节点 preorder_root = preorder_left # 在中序遍历中定位根节点 inorder_root = index[preorder[preorder_root]] # 先把根节点建立出来 root = TreeNode(preorder[preorder_root]) # 得到左子树中的节点数目 size_left_subtree = inorder_root - inorder_left # 递归地构造左子树，并连接到根节点 # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素 root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1) # 递归地构造右子树，并连接到根节点 # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素 root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right) return root n = len(preorder) # 构造哈希映射，帮助我们快速定位根节点 index = {element: i for i, element in enumerate(inorder)} return myBuildTree(0, n - 1, 0, n - 1)
方法二：递归（2个参数）
对 preorder进行pop(0)，因为第一节点总是根节点。注意是先构建左子树
python写法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: def mybuild(in_left,in_right): if in_left>in_right: return None val = preorder.pop(0) in_root = index[val] root = TreeNode(val) root.left = mybuild(in_left,in_root-1) root.right = mybuild(in_root+1,in_right) return root index = {element:i for i,element in enumerate(inorder)} return mybuild(0,len(inorder)-1)
c++写法
class Solution { public: unordered_map<int,int> map; vector<int> preorder; vector<int> inorder; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { this->preorder=preorder; this->inorder=inorder; for(int i=0;i<inorder.size();i++){ map[inorder[i]]=i; } return helper(0,inorder.size()-1); } TreeNode* helper(int left,int right){ if(left>right) return nullptr; int val=preorder.front(); preorder.erase(preorder.begin()); int mid=map[val]; TreeNode* root=new TreeNode(val); root->left=helper(left,mid-1); root->right=helper(mid+1,right); return root; } };
