重建二叉树（C++牛客网）

男娘i 2022-11-18 10:53 130阅读 0赞

解题思路：

（1）注意先序遍历和中序遍历中根结点的位置

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
            vector<int> pre_left,pre_right,vin_left,vin_right;
            if(pre.size()==0) return nullptr;
            TreeNode * root=new TreeNode(pre[0]);
            int pos=find(vin.begin(),vin.end(),pre[0])-vin.begin();
            for(int i=0;i<vin.size();i++) {
                if(i<pos) {
                    vin_left.push_back(vin[i]);
                    pre_left.push_back(pre[i+1]);
                } else if(i>pos) {
                    vin_right.push_back(vin[i]);
                    pre_right.push_back(pre[i]);
                }
            }
            TreeNode *left=reConstructBinaryTree(pre_left,vin_left);
            TreeNode *right=reConstructBinaryTree(pre_right,vin_right);
            root->left=left;
            root->right=right;
            
            return root;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客网刷题——二叉树

![ced485cbb11e458d81a746890b32cf3f.gif][] > 文章目录 1.KY11 二叉树遍历 2.二叉树的层序遍历 3.判断一棵树是否是完

╰半夏微凉°/ 2023年10月10日 15:07/ 0 赞/ 10 阅读

相关牛客网刷题——二叉树

![ced485cbb11e458d81a746890b32cf3f.gif][] > 作者：敲代码の流川枫 > > 博客主页：[流川枫的博客][Link 1] > >

旧城等待，/ 2023年10月10日 15:07/ 0 赞/ 9 阅读

相关平衡二叉树（C++牛客网）

解题思路：（1）依次判断每个结点的左右子树是否满足高度差 class Solution { private: bool tag=true;

清疚/ 2022年11月19日 04:20/ 0 赞/ 147 阅读

相关重建二叉树（C++牛客网）

解题思路：（1）注意先序遍历和中序遍历中根结点的位置 / Definition for binary tree struct TreeNo

男娘i/ 2022年11月18日 10:53/ 0 赞/ 131 阅读

相关二叉树的最大深度（C++牛客网）

解题思路：（1）dfs class Solution { private: int max_h=0; public:

超、凢脫俗/ 2022年11月18日 04:51/ 0 赞/ 27 阅读

相关牛客网---二叉树（python实现）

王霸之气一：重建二叉树：二：判断二叉树是否对称（镜像二叉树）：三：转换成镜像二叉树：

谁践踏了优雅/ 2022年11月05日 08:37/ 0 赞/ 133 阅读

相关按之字形顺序打印二叉树 (C++牛客网）

（1）队列，翻转 / struct TreeNode { int val; struct TreeNode left;

青旅半醒/ 2022年09月11日 15:09/ 0 赞/ 183 阅读

相关牛客题霸 NC12 重建二叉树

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6 解决方案 Go fu

淡淡的烟草味﹌/ 2022年09月03日 12:22/ 0 赞/ 126 阅读

相关 [牛客剑指offer]重建二叉树

题目连接：https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6 题目大意：给定二叉树的先序遍历

ゞ浴缸里的玫瑰/ 2021年12月11日 04:45/ 0 赞/ 194 阅读

相关牛客网刷题——重建二叉树（剑指offer）

2018.1.6加油！题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序

电玩女神/ 2021年10月09日 03:44/ 0 赞/ 305 阅读