Karl's Nest
0%

leetcode-day-20

Posted on In
Day-20 Construct Binary Search Tree from Preorder Traversal

LeetCode 30 days Challenge - Day 20

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

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:

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

Note:

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

Solution

题目要求分析：给定一个二叉搜索树的前序遍历序列，要求还原该二叉树。

解法：

本题只要了解：

  1. 二叉搜索树的特性：
    1. 对任意结点，其结点值永远满足（如果存在）：左儿子 < 根 < 右儿子；
    2. 由此推出，左子树任意值 < 根 < 右子树任意值；
  2. 前序遍历：根 -> 左 -> 右 顺序进行遍历。

由此，总结还原的思想是：

  1. 对当前序列，第一个值是根结点，剩余序列中，比第一个值小的是左子树，剩余为右子树。
  2. 递归操作即可，当序列只有一个元素时，直接返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode* build(vector<int>& preorder, int l, int r) {
    if (l == r) return new TreeNode(preorder[l]);
    TreeNode* root = new TreeNode(preorder[l]);
    int i = l + 1;
    while (i <= r && preorder[i] < root->val) i++;
    root->left = (i == l + 1) ? NULL : build(preorder, l + 1, i - 1);
    root->right = (i > r) ? NULL : build(preorder, i, r);
    return root;
}

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

传送门：Construct Binary Search Tree from Preorder Traversal

Karl