题解 | #二叉树中和为某一值的路径(一)#
二叉树中和为某一值的路径(一)
http://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
// 递归,把sum根据本级节点的值调整后向下传,把是否有符合题意的路径布尔值向上抛,终止条件:空节点或找到路径
// 时空复杂度:O(n)
public class Solution {
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if (root == null)
return false;
if (root.val == sum && root.left == null && root.right == null)
return true;
return (hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val));
}
}