剑指offer-JZ4

重建二叉树

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

c++
本题是标准的二叉树重建任务,
利用递归的思路进行重构;
其中需要利用到前序和中序的特点,
前序pre:[root, left, right]
中序vin:[left, root, right];
因此对一个root节点的构建思路:
1---判断是否为空,边界条件
2---找到root的位置
遍历中序,判断vin[i] == pre[0];
得到 root_index
然后构建,左右:
---vin左: [0-------root_index-1]
---pre左:[1--------root_index]


---vin右:[root_index+1------end]
---pre右:[root_index+1------end]


递归构建
(pre左,vin左) (pre右,vin右)

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (vin.size() == 0){
            return NULL;
        }
        TreeNode* root = new TreeNode(pre[0]); // defined  tree root
        vector<int> pre_left, pre_right, vin_left, vin_right; // difine and record tree infor 
        // find root index in vin
        int root_ind=0;
        for(int ind=0; ind<vin.size(); ind++){
            if (vin[ind] == pre[0]){
                root_ind=ind;
                break;
            }
        }
        // update right lefte
        for(int i=0; i<root_ind; i++){
            vin_left.push_back(vin[i]);
            pre_left.push_back(pre[i+1]);//the first is root, need plus 1
        }
        for(int i=root_ind+1; i<vin.size(); i++){
            vin_right.push_back(vin[i]);
            pre_right.push_back(pre[i]);
        }
        // 递归
        root->left = reConstructBinaryTree(pre_left, vin_left);
        root->right = reConstructBinaryTree(pre_right, vin_right);
        return root;
    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议