Leetcode題解 Python & C#：四月挑戰DAY20 Construct Binary Search Tree from Preorder Traversal

給一串依 preorder 順序遍歷二分樹的值，要還原成二分樹，並回傳根。

這二分樹是嚴格的那種，代表左邊子樹皆小於自身，右邊皆大於自身。

依照 preorder 的順序，先自身，再左邊，再右邊。還原也依此進行。

說到要依順序還原，不管是哪種，都要有保留父節的規劃，因為子節是沒辦法往上回溯的。(或者使用遞迴函數)

※一開始先將 root 生成，最後要回傳它。

這裡使用 stack 的概念來保存父節，一旦目前迴圈的值小於 stack[-1] ，那就添加至左邊，並加入該節至 stack。

如果該節大於 stack[-1]，則檢查 stack[-2] 是否小於目前的值，是則不斷刪去 stack[-1] 直到 stack[-2] 大於目前的值或 stack 只剩一個。

然後把該節指派給 stack[-1].rihgt 後刪除 stack[-1]，並添加該節至 stack 中。

這做法類似實際 preorder 的途徑。

Python3

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;
    }
}