[LeetCode] 1008. Construct Binary Search Tree from Preorder Traversal

[grandyang]

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 Traversal，Construct 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 同步地址:

#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 题目讲解汇总(持续更新中...)