IT源码网

重建二叉树讲解

leader 2020年10月29日 编程语言 255 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; 
    } 
};

 

发布评论

分享到:

IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

无重复字符的最长子串和最小覆盖子串(滑动窗口法)讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。