Construct Binary Search Tree from Preorder Traversal（C++前序遍历构造二叉搜索树）

ゝ一世哀愁。 2022-12-30 08:00 102阅读 0赞

解题思路：

（1）递归，小于数组第一个元素的构建左子树，大于数组第一个元素的构建右子树

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* bstFromPreorder(vector<int>& preorder) {
            vector<int> pre,back;
            for(int i=1;i<preorder.size();i++) {
                if(preorder[i]<preorder[0]) pre.push_back(preorder[i]);
                else back.push_back(preorder[i]);
            }
            
            TreeNode *root = new TreeNode(preorder[0]);
            if(!pre.empty()) root->left=bstFromPreorder(pre);
            else root->left=NULL;
            
            if(!back.empty()) root->right=bstFromPreorder(back);
            else root->right=NULL;
            
            return root;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 Construct Binary Search Tree from Preorder Traversal（C++前序遍历构造二叉搜索树）

解题思路：（1）递归，小于数组第一个元素的构建左子树，大于数组第一个元素的构建右子树 / Definition for a binary tree n

ゝ一世哀愁。/ 2022年12月30日 08:00/ 0 赞/ 103 阅读

相关 1008. 前序遍历构造二叉搜索树

题目来源 [1008. 前序遍历构造二叉搜索树][1008.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVp

左手的ㄟ右手/ 2022年12月22日 08:52/ 0 赞/ 106 阅读

相关 LeetCode：144.Binary Tree PreOrder Traversal（二叉树前序遍历）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

太过爱你忘了你带给我的痛/ 2022年12月11日 12:18/ 0 赞/ 123 阅读

相关 Construct Binary Tree from Preorder and Inorder Traversal（C++从前序与中序遍历序列构造二叉树）

（1）递归 / Definition for a binary tree node. struct TreeNode {

淩亂°似流年/ 2022年10月13日 02:50/ 0 赞/ 6 阅读

相关 Leetcode: Binary Tree Preorder Traversal（二叉树前序遍历）

题目： Given a binary tree, return the preorder traversal of its nodes’ values. For exam

忘是亡心i/ 2022年08月07日 10:55/ 0 赞/ 6 阅读

相关 144. Binary Tree Preorder Traversal （二叉树的先序遍历）

Given a binary tree, return the preorder traversal of its nodes' values. For example:

桃扇骨/ 2022年07月14日 06:29/ 0 赞/ 52 阅读

相关 [leetcode-二叉树先序遍历]--144.Binary Tree Preorder Traversal

Question 144. Binary Tree Preorder Traversal > Given a binary tree, return the preorder

喜欢ヅ旅行/ 2022年07月12日 03:27/ 0 赞/ 124 阅读

相关 [Leetcode][python]Binary Tree Preorder Traversal/二叉树的前序遍历

题目大意二叉树前序遍历挑战：迭代解题解题思路递归简单迭代思路：见下方代码前　　1 　　　　　　　/ \

港控/mmm°/ 2022年06月11日 08:17/ 0 赞/ 138 阅读

相关 leetcode 144. Binary Tree Preorder Traversal 二叉树前序遍历 + 深度优先遍历DFS

Given a binary tree, return the preorder traversal of its nodes’ values. For example:

谁借莪１个温暖的怀抱￠/ 2022年06月08日 04:58/ 0 赞/ 176 阅读

相关 LeetCode 144.Binary Tree Preorder Traversal (二叉树的前序遍历)

题目描述：给定一个二叉树，返回它的前序遍历。示例: 输入: [1,null,2,3] 1 \ 2

妖狐艹你老母/ 2022年05月08日 13:33/ 0 赞/ 167 阅读