摘要:題目要求假設有一個二叉樹,和一個目標值,如果存在一條從根節點到葉節點的路徑,該路徑上所有節點上的值的和恰好等于該目標值,則返回,否則返回方法的輸入為根節點和目標值例如假設有一顆二叉樹如下,目標值為,結果返回,因為存在一條路徑其和為思路
題目要求
假設有一個二叉樹,和一個目標值,如果存在一條從根節點到葉節點的路徑,該路徑上所有節點上的值的和恰好等于該目標值,則返回true,否則返回FALSE
方法的輸入為根節點和目標值
例如:假設有一顆二叉樹如下,目標值為22,結果返回true,因為存在一條路徑5->4->11->2其和為22
5 / 4 8 / / 11 13 4 / 7 2 1思路一 : 遞歸
/** * @author rale * *Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. *For example: *Given the below binary tree and sum = 22, 5 / 4 8 / / 11 13 4 / 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. */ public class PathSum_112 { public boolean hasPathSum(TreeNode root, int sum) { if(root==null){ return false; } sum -= root.val; if(root.left==null && root.right==null && sum==0){ return true; } return hasPathSum(root.left, sum) || hasPathSum(root.right, sum); } public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }思路二:循環(使用堆棧)
public class PathSum_112 { public boolean hasPathSum2(TreeNode root, int sum) { Stackstack = new Stack<> (); stack.push(root) ; while (!stack.isEmpty() && root != null){ TreeNode cur = stack.pop() ; if (cur.left == null && cur.right == null){ if (cur.val == sum ) return true ; } if (cur.right != null) { cur.right.val = cur.val + cur.right.val ; stack.push(cur.right) ; } if (cur.left != null) { cur.left.val = cur.val + cur.left.val; stack.push(cur.left); } } return false ; } public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }
想要了解更多開發技術,面試教程以及互聯網公司內推,歡迎關注我的微信公眾號!將會不定期的發放福利哦~
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66907.html
摘要:小鹿題目路徑總和給定一個二叉樹和一個目標和,判斷該樹中是否存在根節點到葉子節點的路徑,這條路徑上所有節點值相加等于目標和。說明葉子節點是指沒有子節點的節點。 Time:2019/4/26Title: Path SumDifficulty: EasyAuthor: 小鹿 題目:Path Sum(路徑總和) Given a binary tree and a sum, determin...
摘要: 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...
摘要:自己沒事刷的一些的題目,若有更好的解法,希望能夠一起探討項目地址 自己沒事刷的一些LeetCode的題目,若有更好的解法,希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
摘要:月下半旬攻略道題,目前已攻略題。目前簡單難度攻略已經到題,所以后面會調整自己,在刷算法與數據結構的同時,攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區別...
摘要:在線網站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目,語言 JavaScript。 在線網站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...
閱讀 1654·2019-08-30 13:04
閱讀 2205·2019-08-30 12:59
閱讀 1764·2019-08-29 18:34
閱讀 1857·2019-08-29 17:31
閱讀 1255·2019-08-29 15:42
閱讀 3530·2019-08-29 15:37
閱讀 2857·2019-08-29 13:45
閱讀 2771·2019-08-26 13:57