重建二叉树解析

无情阅读：841 2020-10-29 21:52:27 评论：0

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

例如，给出

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

3
/ \
9 20
/ \
15 7

限制：

0 <= 节点个数 <= 5000

解:树一般都用递归的方法，这道题解题的关键是找到根节点在前序和中序的位置及关系

/** 
 * Definition for a binary tree node. 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */ 
class Solution { 
public: 
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
        if(preorder.size()==0||inorder.size()==0) 
            return nullptr; 
        int i_medpos=0; 
        while(i_medpos<inorder.size()) 
        { 
            if(inorder[i_medpos]==preorder[0]) 
                break; 
            i_medpos++; 
        } 
        TreeNode *root=new TreeNode(preorder[0]); 
        //前序数组中去掉根节点,中序数组中根节点的下标，在前序节点中此下标前的都是根节点的左子树 
        vector<int> left_pre(preorder.begin()+1,preorder.begin()+i_medpos+1); 
        vector<int> right_pre(preorder.begin()+i_medpos+1,preorder.end()); 
 
        vector<int> left_in(inorder.begin(),inorder.begin()+i_medpos); 
        //中序数组中去掉根节点 
        vector<int> right_in(inorder.begin()+i_medpos+1,inorder.end()); 
 
        root->left=buildTree(left_pre,left_in); 
        root->right=buildTree(right_pre,right_in); 
        return root; 
    } 
};