1008.Construct Binary Search Tree from Preorder Traversal¶

1008.Construct Binary Search Tree from Preorder Traversal¶

Tags: Medium Tree

Links: https://leetcode.com/problems/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 of node.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.)

Example 1:

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

Note:

1 <= preorder.length <= 100
The values of preorder are distinct.

/**
 * 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* bstFromPreorder(vector<int>& preorder) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = preorder.size();
        if (!n) return NULL;
        return build(preorder, 0, n - 1);
    }

    TreeNode *build(vector<int> & preorder, int start, int end)
    {
        TreeNode *root = new TreeNode(preorder[start]);
        int pos = start;
        while (pos <= end) {
            if (preorder[pos] > preorder[start]) break;
            else ++pos;
        }

        TreeNode *left = NULL, *right = NULL;
        if (pos - 1 - start > 0) left = build(preorder, start + 1, pos - 1);
        if (end - pos + 1 > 0) right = build(preorder, pos, end);
        root -> left = left;
        root -> right = right;

        return root;
    }
};

按理说构建二叉树需要至少需要一个中序遍历，前序和后序选一个，这道题目不一样的是，构建的是一颗排序二叉树，比如题目里的[8,5,1,7,10,12]，会发现10，12肯定在右子树，那么就很类似将链表转为二叉树的操作，找到第一个大于起始节点的值，然后递归的去实现，只需要注意一下边界条件即可。

另外如果需要处理输入和输出，那么可以这么写：

#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
};

TreeNode *build(vector<int> & preorder, int start, int end)
{
    TreeNode *root = new TreeNode(preorder[start]);
    int pos = start;
    while (pos <= end) {
        if (preorder[pos] > preorder[start]) break;
        else ++pos;
    }

    TreeNode *left = NULL, *right = NULL;
    if (pos - 1 - start > 0) left = build(preorder, start + 1, pos - 1);
    if (end - pos + 1 > 0) right = build(preorder, pos, end);
    root -> left = left;
    root -> right = right;

    return root;
}

TreeNode* bstFromPreorder(vector<int>& preorder) {
    int n = preorder.size();
    if (!n) return NULL;
    return build(preorder, 0, n - 1);
}

void print(TreeNode *root)
{
    if (!root) {
        cout << "NULL" << endl;
        return;
    }

    queue<TreeNode *> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode *tmp = q.front(); q.pop();
        if (tmp) cout << tmp -> val << ' ';
        else {
            cout << "NULL" << ' ';
            continue;
        }

        if (!tmp -> left && !tmp -> right) continue;
        q.push(tmp -> left);
        q.push(tmp -> right);
    }

    cout << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> preOrder;
    int num;
    while (cin >> num) preOrder.push_back(num);
    TreeNode *root = bstFromPreorder(preOrder);
    print(root);

    return 0;
}