1008. Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant ofnode.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

It’s guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Constraints:

  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 10^8
  • The values of preorder are distinct.

这道题让我们从一个数组来重建一棵二叉搜索树,同时说明了这个数组是先序遍历二叉树后得到的。首先要明白的是二叉搜索树的性质,是左子结点值小于根结点小于右子结点,正是因为有这样的特点,才使得从一种遍历顺序上重建变的可能。若是普通的二叉树,则至少需要两种遍历顺序的数组,比如之前的 Construct Binary Tree from Preorder and Postorder TraversalConstruct Binary Tree from Inorder and Postorder Traversal,和 Construct Binary Tree from Preorder and Inorder Traversal。再来分析下这个先序数组有什么特点,先序是根左右的顺序,则第一个结点肯定是根结点,而根据二叉搜索树的特点,接下来第一个大于根结点值的数一定是右子结点,而中间的数字都是左子树中的值,这样就可以将左右子树分开了,再分别调用递归函数就可以建成整个树了。有了思路,代码就很好写了,先对 preorder 判空,若不为空则用第一个数字建立一个根结点,然后遍历数组,找到第一个大于根结点值的数字,将左右子树的数组提取来,分别调用递归函数,连接到根结点的左右子结点即可,参见代码如下:

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        if (preorder.empty()) return nullptr;
        TreeNode *node = new TreeNode(preorder[0]);
        int i = 0, n = preorder.size();
        for (i = 1; i < n; ++i) {
            if (preorder[i] > preorder[0]) break;
        }
        vector<int> left(preorder.begin() + 1, preorder.begin() + i);
        vector<int> right(preorder.begin() + i, preorder.end());
        node->left = bstFromPreorder(left);
        node->right = bstFromPreorder(right);
        return node;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1008

类似题目:

Construct Binary Tree from Preorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

参考资料:

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/discuss/252754/Java-Stack-Iterative-Solution

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/discuss/252232/JavaC%2B%2BPython-O(N)-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation