Construct Binary Search Tree From Preorder Traversal: Xây BST Từ Preorder

Đề bài: Cho preorder traversal của BST, xây lại cây. Preorder: root, left, right. BST property: left < root < right.

Ví dụ: [8,5,1,7,10,12] → BST root=8, left subtree=[5,1,7], right=[10,12].

Giải pháp 1: Stack (O(n)) - Tối Ưu

Duyệt preorder, dùng stack lưu "ancestors đang chờ right child".

• Root = preorder[0], push stack.
• Với mỗi val tiếp theo:
  • Tạo node.
  • Nếu val < stack.top.val → left child của stack.top.
  • Ngược lại: pop stack cho đến khi stack.top.val > val (hoặc stack rỗng). Node popped cuối = parent, val = right child của nó.
  • Push node mới.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def bstFromPreorder(self, preorder: list[int]) -> TreeNode:
        root = TreeNode(preorder[0])
        stack = [root]
        
        for val in preorder[1:]:
            node = TreeNode(val)
            if val < stack[-1].val:
                stack[-1].left = node
            else:
                parent = None
                while stack and val > stack[-1].val:
                    parent = stack.pop()
                parent.right = node
            stack.append(node)
        
        return root

Giải pháp 2: Recursive Bounds (O(n))

Duyệt preorder với index global, mỗi call có bound (min, max).

class Solution:
    def bstFromPreorder(self, preorder: list[int]) -> TreeNode:
        self.idx = 0
        def build(lower=float('-inf'), upper=float('inf')):
            if self.idx == len(preorder):
                return None
            val = preorder[self.idx]
            if not (lower < val < upper):
                return None
            self.idx += 1
            node = TreeNode(val)
            node.left = build(lower, val)
            node.right = build(val, upper)
            return node
        return build()

Phân tích

• Cả 2 đều O(n) time, O(h) space (stack/recursion).
• Stack iterative: dễ hiểu logic BST property.
• Recursive bounds: ngắn gọn, elegant.

Kết luận

Xây BST từ preorder tận dụng tính chất: left subtree values < root < right subtree values. Stack method mô phỏng recursion explicit.