深度優先搜尋 (DFS)

解題思路

1. 節點訪問：我們會訪問每一個節點，並以該節點作為起始點。
2. 路徑探索：對於每一個起始節點，我們會探索所有向下延伸的路徑。這是通過遞迴遍歷來實現的。
3. 計算結果：最後，我們將所有節點的路徑數量加總，得到的總和就是我們的答案。

這種方法基本上是在窮舉所有可能的路徑，並計算有多少種不同的路徑可以選擇。

1. 定義函數：首先，我們定義一個函數 find(p,sum)，這個函數表示以節點 p 為起點，向下的路徑總和為 sum 的路徑數目。
2. 求解 find：對於二元樹上的每個節點 p，我們都計算 find(p,targetSum)。這個過程中，我們會遞迴地向下搜尋每一條可能的路徑。我們先檢查當前節點 p 的值是否剛好等於 targetSum。 如果是的話，以節點 p 為起點，向下的路徑總和為 sum 的路徑數目就是 1。 如果不是的話，假設當前節點 p 的值為 val，我們就對左子樹和右子樹進行遞迴搜尋，分別求出 find(p.left,targetSum−val) 和 find(p.right,targetSum−val)。然後，節點 p 的 find(p,targetSum) 就等於這兩個值的和。
3. 計算結果：最後，我們將所有節點的 rootSum(p,sum) 加總起來，得到的總和就是我們要找的答案。

別閉門造車，一起準備面試吧！
在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！
我們將幫助您撰寫一份出色的履歷表，讓您在眾多求職者中脫穎而出。我們將為您提供專業的建議和指導，幫助您在履歷上呈現最完美的自己。如果心動的話，就別猶豫啦！趕快把握機會，動動手指投遞履歷吧！立即加入 Line 讀書會，和大家一起實現夢想！

履歷諮詢	加入讀書會 (邀請碼：4115)

程式

class Solution {
    fun pathSum(root: TreeNode?, targetSum: Int): Int {
        return rootSum(root, targetSum.toLong()).toInt()
    }

    private fun find(root: TreeNode?, targetSum: Long): Long {
        return if (root == null) 0
        else {
            var result = 0L
            if (root.`val`.toLong() == targetSum) {
                result++
            }
            result += find(root.left, targetSum - root.`val`)
            result += find(root.right, targetSum - root.`val`)
            result
        }
    }

    private fun rootSum(p: TreeNode?, targetSum: Long): Long {
        return if (p == null) 0
        else {
            var result = 0L
            result += find(p, targetSum)
            result += rootSum(p.left, targetSum)
            result += rootSum(p.right, targetSum)
            result
        }
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是二元樹的節點數量。這是因為我們需要對每一個節點計算以該節點為起點的路徑數量。在這個過程中，我們需要遍歷該節點的所有子節點，所以每一個節點的計算時間最多為 。由於我們需要對所有 個節點都進行這樣的計算，所以總的時間複雜度就是 。

• 空間複雜度:
  ，這是因為我們使用了遞迴，需要在堆疊上開空間來儲存遞迴呼叫的資訊。在最壞的情況下，當二元樹退化為鏈結串列時，遞迴深度可能達到 ，因此空間複雜度為 。

　更多演算法題解，一起來學習！

別閉門造車，一起準備面試吧！

在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！

履歷諮詢	加入讀書會 (邀請碼：4115)