路径总和00
题目链接
路径总和
题目描述
注意点
- 树中节点的数目在范围 [0, 5000] 内
- -1000 <= Node.val <= 1000
解答思路
- 要判断是否有一条从根节点开始到叶子节点节点总和为targetSum的路径，首先想到使用深度优先遍历，不断递归找到叶子节点且保存该路径的路径总和，如果找到了一条路径总和为targetSum，则直接返回true
代码
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}targetSum -= root.val;if (root.left == null && root.right == null) {return targetSum == 0;}return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);}
}
关键点
- 深度优先遍历的思想