30daychallenge (20) | Construct Binary Search Tree from Preorder Traversal

ecall 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. 1 <= preorder.length <= 100
2. The values of preorder are distinct.

Đồ thị và cây là hai mảng yếu nhất của tôi, chắc chắn tôi phải làm nhiều những bài như thế này hơn. Trong bài toán này, nút gốc root luôn là nút đầu mảng theo tính chất của preorder.

Sẽ có hai trường hợp xảy ra khi duyệt mảng sau nút gốc là nhỏ hơn hoặc lớn hơn root. Trường hợp nhỏ hơn, ta thêm vào bên trái root, ngược lại ta thêm vào bên phải.

Như ví dụ trên: 5 < 8 nên 8.left = 5 . 1 <5 nên 5.left = 1. Như vậy, ta có một stack để lưu nốt hiện thời. Phần tạo cây bên phải đã được giải quyết:

 stack.peek().left = preorder[i]; stack.push(new TreeNode(preorder(i));

Trường hợp còn lại là khi 7 > 1 (Stack giờ đang là 8 5 1). Ta sẽ lưu curr = pop stack cho đến khi hết stack , hoặc khi gặp một phần tử lớn hơn 7. Ở đây là 8 - > curr = 5. Vậy:

curr.right = 7 và stack.push(7).

Được rồi, còn đây là code trên Java:


Hết rồi, hẹn gặp Leetcode vào ngày mai. Cảm ơn bạn !