溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下LeetCode如何實現路徑總和，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和。
說明: 葉子節點是指沒有子節點的節點。
示例: 給定如下二叉樹，以及目標和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
返回 true, 因為存在目標和為 22 的根節點到葉子節點的路徑 5->4->11->2。
標簽：深度優先遍歷
遞歸終止條件：
當前節點為null時返回false
當前節點為根節點時 且 路徑和等于目標和 則返回true
遞歸過程：不斷判斷判斷左右子樹
注意點：這里涉及到短路問題，也就是當發現了某一條路徑和滿足條件時，就應該結束遞歸，故而下面的解法中使用了或運算，這樣不用判斷全部路徑，有滿足條件則結束，減少時間復雜度
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null ) return false; if(root.left == null && root.right == null && sum == root.val) return true; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }}以上是“LeetCode如何實現路徑總和”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
