112. 路徑總和

題目描述

給定一棵二元樹的根節點和整數 targetSum，判斷是否存在從根到葉節點的路徑，使得路徑上所有節點值之和等於 targetSum。葉節點為無左右子節點的節點。

解法思路

1. 使用 DFS 遞迴，每層將 target 扣掉當前節點值傳給子節點
2. 空節點（None）回傳 False
3. 到達葉節點時判斷 target == node.val，符合則回傳 True
4. 非葉節點回傳 dfs(left, target-val) or dfs(right, target-val)

複雜度分析

• 時間複雜度：O(n)
• 空間複雜度：O(h)，h 為樹的高度