重建二叉树分析

无情 阅读:399 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; 
    } 
};

 

标签:C++
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号