1008-construct-binary-search-tree-from-preorder-traversal.md

1008. Construct Binary Search Tree from Preorder Traversal - 先序遍历构造二叉树

返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）

 

示例：

输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

 

提示：

1. 1 <= preorder.length <= 100
2. 先序 preorder 中的值是不同的。

---

题目标签：Tree

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	8 ms	11 MB

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int>& pre, int pst, int ped, vector<int>& in, int ist, int ied) {
        if (ped <= pst || ied <= ist || pst >= (int)pre.size()) 
            return NULL;
        TreeNode* root = new TreeNode(pre[pst]);
        int iroot = -1;
        for (int i = ist; i < ied; i++) {
            if (in[i] == pre[pst]) {
                iroot = i;
                break;
            }
        }
        root->left = build(pre, pst + 1, pst + 1 + iroot - ist, in, ist, iroot);
        root->right = build(pre, pst + 1 + iroot - ist, ped, in, iroot + 1, ied);
        return root;
    }

    TreeNode* bstFromPreorder(vector<int>& preorder) {
        vector<int> inorder(preorder);
        sort(inorder.begin(), inorder.end());
        if (!preorder.empty()) {
            return build(preorder, 0, preorder.size(), inorder, 0, inorder.size());
        } else {
            return NULL;
        }
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();