給一串依 preorder 順序遍歷二分樹的值，要還原成二分樹，並回傳根。
這二分樹是嚴格的那種，代表左邊子樹皆小於自身，右邊皆大於自身。
依照 preorder 的順序，先自身，再左邊，再右邊。還原也依此進行。
說到要依順序還原，不管是哪種，都要有保留父節的規劃，因為子節是沒辦法往上回溯的。(或者使用遞迴函數)
※一開始先將 root 生成，最後要回傳它。
這裡使用 stack 的概念來保存父節，一旦目前迴圈的值小於 stack[-1] ，那就添加至左邊，並加入該節至 stack。
如果該節大於 stack[-1]，則檢查 stack[-2] 是否小於目前的值，是則不斷刪去 stack[-1] 直到 stack[-2] 大於目前的值或 stack 只剩一個。
然後把該節指派給 stack[-1].rihgt 後刪除 stack[-1]，並添加該節至 stack 中。
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
root = TreeNode(preorder.pop(0))
stack = [root]
while preorder:
node = TreeNode(preorder.pop(0))
if node.val < stack[-1].val:
stack[-1].left = node
stack.append(node)
else:
while len(stack) >= 2 and stack[-2].val < node.val:
del stack[-1]
stack.pop().right = node
stack.append(node)
return root
C#
public class Solution {
public TreeNode BstFromPreorder(int[] preorder) {
TreeNode root = new TreeNode(preorder[0]);
List stack = new List{root};
for(int i = 1; i < preorder.Length; i++)
{
TreeNode node = new TreeNode(preorder[i]);
if(node.val < stack[stack.Count-1].val)
{
stack[stack.Count-1].left = node;
stack.Add(node);
}
else
{
while(stack.Count>=2 && stack[stack.Count-2].val < node.val)
stack.RemoveAt(stack.Count-1);
stack[stack.Count-1].right = node;
stack.RemoveAt(stack.Count-1);
stack.Add(node);
}
}
return root;
}
}
除了 stack ，也可以使用「遞迴」解決。
Python 搭配二分搜查
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
if not preorder: return None
def nextNode(l, r):
if l==r: return None
node = TreeNode(preorder[l])
l2, r2 = l+1, r
while l2 < r2:
m = (r2-l2)//2 + l2
if preorder[m] < node.val:
l2 = m+1
else:
r2 = m
node.left = nextNode(l+1, l2)
node.right = nextNode(l2, r)
return node
return nextNode(0, len(preorder))
C# Linq篩選
public class Solution {
public TreeNode BstFromPreorder(int[] preorder) {
if(preorder.Length == 0){return null;}
TreeNode node = new TreeNode(preorder[0]);
node.left = BstFromPreorder((from num in preorder where num < preorder[0] select num).ToArray());
node.right = BstFromPreorder((from num in preorder where num > preorder[0] select num).ToArray());
return node;
}
}