剑指Offer - 面试题7. 重建二叉树（递归）

Michael阿明

发布于 2020-07-13 16:06:14

2650

发布于 2020-07-13 16:06:14

1. 题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7
 
限制：
0 <= 节点个数 <= 5000

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

2. 解题

请参考上面链接文章，不再赘述。

class Solution {
	unordered_map<int,int> in;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty())
        	return NULL;
        int i, n = preorder.size();
        for(i = 0; i < n; ++i)
        	in[inorder[i]] = i;
        return build(preorder,0,n-1,inorder,0,n-1);
    }

    TreeNode* build(vector<int>& preorder, int sp, int ep, vector<int>& inorder, int si, int ei)
    {
    	if(ep-sp<0)
    		return NULL;
    	TreeNode* root = new TreeNode(preorder[sp]);
    	int Proot = in[preorder[sp]];
    	int leftlen = Proot-si;
    	int rightLen = ei-Proot;
    	root->left = build(preorder,sp+1,sp+leftlen,inorder,si,Proot-1);
    	root->right = build(preorder,sp+leftlen+1,sp+leftlen+rightLen,inorder,Proot+1,ei);
    	return root;
    }
};