題目出處

596 · Minimum Subtree

難度

easy

個人範例程式碼

from lintcode import (
    TreeNode,
)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the root of the minimum subtree
    """    
    def __init__(self): # class variable (global in class)
        self.subtree = TreeNode(0)
        self.subtree_sum = float("inf")

    def find_subtree(self, root: TreeNode) -> TreeNode:
        self.dfs(root)
        return self.subtree

    def dfs(self, root):
        if not root:
            return 0

        thissum = self.dfs(root.left) + self.dfs(root.right) + root.val
        if thissum < self.subtree_sum:
            self.subtree_sum = thissum
            self.subtree = root

        return thissum

算法說明

基礎的 DFS 用來 traverse Tree 裡面的內容，這次是從底下算上來，慢慢地找最小總和。

這邊我們為了方便處理，我們多寫了一個 「def init(self)」給他，
定義了在此 class function 裡面的 global 變數。

不過這樣的寫法不確定好不好，
畢竟題目說不定本來就有內建了 init(self) 在裡面，
而只希望我們調用題目所給的 template「def find_subtree(self, root: TreeNode) -> TreeNode:」並修改這之後的內容。

更新：其實這部分做點小修改就行，我們把具有 global 功能的 self.subtree、self.subtree_sum，
定義於 「def find_subtree()」即可。

def __init__(self): # class variable (global in class)
    self.subtree = TreeNode(0)
    self.subtree_sum = float("inf")

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

x

Boundary conditions

end of recursion

dfs 直到最 None 的節點，回傳 0

define of recursion

每個 node 的和，等於「左子樹和 + 右子樹和 + 自己」

thissum = self.dfs(root.left) + self.dfs(root.right) + root.val

每次都與 global 的 self.subtree_sum 比較，
如果比較小，就更新 node 與 新的最小 sum。

if thissum < self.subtree_sum:
    self.subtree_sum = thissum
    self.subtree = root

split of recursion

我們在上述一併做掉了，請見

thissum = self.dfs(root.left) + self.dfs(root.right) + root.val

Reference