Leetcode-Binary Tree 解題心得

Leetcode-Binary Tree 解題心得¶

先說binary tree的最基本架構

class TreeNode:     def __init__(self, val=0, left=None, right=None):         self.val = val         self.left = left         self.right = right

上圖擷取自Leetcode

可以看到一個圓圈我們稱之為node

最常見的node帶有幾個特性:

val: 圓圈中顯示的值

left/right會指向node的子node，稱之為binary 就是因為他只能夠有兩隻腳，如果更多，就不能稱之為binary tree。

上圖的3只有指向6還可以稱之為binary tree嗎? 他還是個合法的tree，因為3這個node本身還是有left and right，只是right他指向None 所以圖中不顯示

以Leet code top interview 150最常出現的題型有

基本應用，可能去算node 最大深度，或是節點數之類，對tree本身不做改動，例如問最大深度，這時候用一個n去往下走的時候+1，找最大值
在這類題型最常用的就是bfs or dfs去把所有node走訪一遍

# 104. Maximum Depth of Binary Tree# 題目:給定一個binary tree，問最深的深度為何# 想法: 一個bfs去走訪所有node，的左跟右，以及當前深度，一旦遇到None 回傳當下最大值class Solution:    def maxDepth(self, root: Optional[TreeNode]) -> int:        def bfs(node, n):            if not node:                return n            r = bfs(node.right, n+1)            l = bfs(node.left, n+1)            return max(r,l)        return bfs(root, 0)

2.或是對node去做改動，比方說把node 壓平為linked list，通常需要多犧牲空間，去把node位址作暫存，在套用linked list的模式去assign即可，須注意binary tree 有兩個子輩，這時候要記得沒用到的指向None

3.還有LCA 最低共同祖先，也蠻常見，概念是如果遇到過的node有符合，就回傳已經遇到的個數，第一次滿足個數的時候，就把該值存進res，並且不要再更動(這樣才是最低共同祖先)

# 236. Lowest Common Ancestor of a Binary Tree# 題目: 給定一個binary tree，以及p/q是tree 裡面的val，問p/q共同的LCA 最小共同祖先# LCA定義:兩個node最快可以有一樣的root# 想法: 在檢查過程中紀錄是否有遇到p/q，有遇到就+1，當檢查值是2的時候，紀錄該val 在res 如果res已經有值，就不去更動class Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':        self.res = None        def bfs(node):            if not node:                return 0            n = bfs(node.left) + bfs(node.right) #get r and l return value            if ((node in [p,q] and n== 1) or n == 2) and (not self.res):                #if n is 1 and current is match or n is 2                 #and res is still empty                self.res = node #Save LCA to res                return 2            elif node in [p,q] or n == 1: return 1 #current match or nis 1            else: return 0 #no matching         bfs(root)        return self.res

在binary tree比較少考慮edge case，但要熟悉val/right/left跟bfs的使用

Leetcode-Binary Tree 解題心得

Leetcode-Binary Tree 解題心得¶

Comments

Leave a Comment