檢查一棵二元樹中是否存在一條從根節點到葉子節點的路徑

 

問題

請用 Python 實現一個函數 has_path，用來檢查一棵二元樹中是否存在一條從根節點到葉子節點的路徑，使得該路徑上所有節點的值之和等於給定的目標值。請提供一個簡單的二元樹結構，以及一些範例測試用例。

解答

以下是 has_path 函數的實現和測試用例：

TreeNode 類別定義

首先，我們定義一個 TreeNode 類別來表示二叉樹的節點：

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

has_path 函數實現

接下來，這是 has_path 函數的實現：

def has_path(root, target):
    if root is None:
        return False
      
    # 檢查是否為葉子節點且其值等於目標
    if root.val == target and root.left is None and root.right is None:
        return True
      
    # 遞歸檢查左子樹和右子樹
    return has_path(root.left, target - root.val) or has_path(root.right, target - root.val)

測試用例

以下是如何創建範例樹並測試 has_path 函數：

def main():
    # 建立一個範例二叉樹：
    #       5
    #      / \
    #     4   8
    #    /   / \
    #   11  13  4
    #   / \      \
    #  7   2      1

    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)

    # 測試案例
    print(has_path(root, 22))  # 預期輸出：True (5 -> 4 -> 11 -> 2)
    print(has_path(root, 26))  # 預期輸出：True (5 -> 8 -> 13)
    print(has_path(root, 18))  # 預期輸出：True (5 -> 8 -> 4 -> 1)
    print(has_path(root, 27))  # 預期輸出：False (沒有這樣的路徑)
    print(has_path(root, 10))  # 預期輸出：False (沒有這樣的路徑)

if __name__ == "__main__":
    main()

測試案例解釋

1. has_path(root, 22)：路徑 5 → 4 → 11 → 2 的和是 22，因此返回 True。
2. has_path(root, 26)：路徑 5 → 8 → 13 的和是 26，因此返回 True。
3. has_path(root, 18)：路徑 5 → 8 → 4 → 1 的和是 18，因此返回 True。
4. has_path(root, 27)：沒有任何路徑的和是 27，因此返回 False。
5. has_path(root, 10)：也沒有任何路徑的和是 10，因此返回 False。

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