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

男娘i 2022-11-18 10:53 163阅读 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 条评论，163人围观）

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

相关阅读

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

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

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

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

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

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

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

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

雨点打透心脏的1/2处/ 2023年10月10日 15:07/ 0 赞/ 10 阅读

相关牛客网-对称二叉树

题目描述请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。牛客网OJ连接：[https://www.no

系统管理员/ 2023年03月01日 09:41/ 0 赞/ 9 阅读

相关牛客网-二叉树的镜像

题目描述操作给定的二叉树，将其变换为源二叉树的镜像。输入描述: 二叉树的镜像定义：源二叉树 8 / 6 10 / \\ / 5 7 9 1

曾经终败给现在/ 2023年03月01日 09:40/ 0 赞/ 10 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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