計算從二元樹的根節點到所有葉子節點的路徑數字的總和

 

問題

實現一個函數 find_sum_of_path_numbers，用來計算從二元樹的根節點到所有葉子節點的路徑數字的總和。每條路徑的數字由沿途的節點值組成。

程式碼實現

以下是 find_sum_of_path_numbers 函數及其輔助函數的實現：

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

def find_sum_of_path_numbers(root):
    return find_root_to_leaf_path_numbers(root, 0)

def find_root_to_leaf_path_numbers(current_node, path_sum):
    if current_node is None:
        return 0
      
    # 計算當前路徑數字
    path_sum = 10 * path_sum + current_node.val
    
    # 如果是葉子節點，返回當前路徑數字
    if current_node.left is None and current_node.right is None:
        return path_sum
      
    # 遞歸計算左子樹和右子樹的路徑數字總和
    return (find_root_to_leaf_path_numbers(current_node.left, path_sum) + 
            find_root_to_leaf_path_numbers(current_node.right, path_sum))

測試範例

以下是如何建立一棵簡單的二叉樹並測試 find_sum_of_path_numbers 函數：

def main():
    # 建立範例二叉樹：
    #       1
    #      / \
    #     0   1
    #    / \   \
    #   1   1   1

    root = TreeNode(1)
    root.left = TreeNode(0)
    root.right = TreeNode(1)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(1)
    root.right.right = TreeNode(1)

    # 計算從根到葉子的路徑數字的總和
    result = find_sum_of_path_numbers(root)
    print(result)  # 預期輸出：312 (101 + 101 + 111)

if __name__ == "__main__":
    main()

測試案例解釋

在這個範例中，樹的結構如下：

      1
     / \
    0   1
   / \   \
  1   1   1

從根到葉子的路徑數字如下：

1. 路徑 1 → 0 → 1 形成數字 101
2. 路徑 1 → 0 → 1 形成數字 101
3. 路徑 1 → 1 → 1 形成數字 111

因此，所有路徑數字的總和是 101 + 101 + 111 = 313。

你可以運行這段程式碼來驗證結果。如果有任何問題或需要進一步的解釋，請隨時告訴我！

資料來源：
https://hackmd.io/@Hsins/depth-first-search