溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“c++路徑之和實例分析”，內容詳細，步驟清晰，細節處理妥當，希望這篇“c++路徑之和實例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
算法：
算法采用遞歸，核心在于如何找到遞歸的終止條件，具體步驟如下：
1.采用遞歸的方式，sum的數值要隨著遍歷過的節點做遞減操作，sum = sum-root.Val2.遞歸的終止條件sum==0是其中之一，如果要求是葉子節點的也需要加上
題目1:路徑總和
代碼實現：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func hasPathSum(root *TreeNode, sum int) bool { if root == nil { return false } // 葉子節點的判斷，排除非葉子節點==sum的情況 if root.Left == nil && root.Right == nil { return sum == root.Val } res := sum - root.Val if hasPathSum(root.Left,res) { return true } if hasPathSum(root.Right,res) { return true } return false}
題目2:路徑總和2
代碼實現：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */var res [][]intfunc pathSum(root *TreeNode, sum int) [][]int { res = [][]int{} // 為了清空 res 上次的數值 if root == nil { return nil } // var res [][]int var tmp []int dfs(root,sum,tmp) return res}func dfs(root *TreeNode, sum int, tmp []int) { if root == nil { return } tmp = append(tmp,root.Val) if sum == root.Val && root.Left == nil && root.Right == nil { r := make([]int, len(tmp)) // 防止tmp對應的共享內容被修改 copy(r, tmp) res = append(res, r) return } dfs(root.Left,sum-root.Val,tmp) dfs(root.Right,sum-root.Val,tmp) return }
題目3:路徑總和3
代碼實現：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func pathSum(root *TreeNode, sum int) int { if root == nil { return 0 } result := countPath(root,sum) result += pathSum(root.Left,sum) result += pathSum(root.Right,sum) return result}func countPath(root *TreeNode, sum int) int { if root == nil { return 0 } count := 0 res := sum - root.Val if res == 0 { count = 1 } return count + countPath(root.Left,res) + countPath(root.Right,res)}/*以當前節點作為頭結點的路徑數量以當前節點的左孩子作為頭結點的路徑數量以當前節點的右孩子作為頭結點的路徑數量*/
讀到這里，這篇“c++路徑之和實例分析”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
