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

給一個以「Preorder」得到的值陣列，重構出二元樹，並回傳 root 。

這是一個嚴謹的二元樹，所以左邊子樹皆小於自身，右邊皆大於自身。

preorder 是以 自身 → 左 → 右 ，因此陣列的第一個元素會是root。

接著下一個會是左邊第一個，直到比root大。

第一個比root大的是右方第一個，直到最後。

因此可用從陣列中篩選(比第一個)大小，並把 solution 當遞迴函式用，完成二元樹的重構。

(因為本題重複過，所以更多說明請點這裡。)

Python

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        if not preorder: return None
        node = TreeNode(preorder[0])
        node.left = self.bstFromPreorder([v for v in preorder if v < node.val])
        node.right = self.bstFromPreorder([v for v in preorder if v > node.val])
        return node    

C#

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