LeetCode 1008 Construct Binary Search Tree from Preorder Traversal

輸入：[8,5,1,7,10,12] 
輸出：
8 
/ \ 
510 
/ \\
1712

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *int val;
 *TreeNode left;
 *TreeNode right;
 *TreeNode(int x) { val = x; }
 * }
 */
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder.length == 0) {
return null;
}
 
Stack<TreeNode> stack = new Stack<>();
TreeNode root = new TreeNode(preorder[0]);
stack.push(root);

for (int i = 1; i < preorder.length; i++) {
TreeNode temp = stack.peek();
int n = preorder[i];
if (n < temp.val) {
temp.left = new TreeNode(n);
stack.push(temp.left);
} else {
TreeNode prev = stack.pop();
while (!stack.isEmpty() && stack.peek().val < n) {
prev = stack.pop();
}
prev.right = new TreeNode(n);
stack.push(prev.right);
}
}
return root;
}
}