LeetCode Binary Search Tree 解題心得

LeetCode Binary Search Tree 解題心得¶

Top Interview 150 關於Binary Search Tree章節心得

BST基本邏輯是左邊的node會小於父輩的值，右邊會大於長相如下

解題上一個要點，照著下面的跑法，就可以從小到大收集到BST的值

res = []        def dfs(node, res):            if not node: return            dfs(node.left, res)            res.append(node.val)            dfs(node.right, res)

因為上面的走法先跑左邊，會先跑到最左邊最底部才會return None然後猜開始append

而題型常見的有找到第n最大/小值，或是找最小值

另一種面向是檢查給定的是不是有效的BST，解題想法是既然知道res的list值一定是遞增的，所以在新增加值之前，先檢查準備要加的值是不是跟res中最後的值還大，如果發生過表示這已經不是有效的BST