LeetCode 112：路径总和

链接

题目：

思路：dfs

思路类似零钱兑换 ，每次向下递归时，把要凑的数sum 减去当前节点root的val，这样即得到下一层需要凑的钱，直到叶子节点的sum等于节点的val即返回true ！

题目说的是根节点到叶子节点！ 所以要遍历到底，使用后序遍历；

单层节点： 判断当前是否是叶子节点，是则判断sum和val是否相等； 若不是叶子节点，继续递归；

base case： 如果root==null ，return false;

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        // 必须要到叶子节点 ！
        // 必须遍历到底！ dfs
        // 遍历到叶子节点后不等于sum，则返回false；
        if(root==null){
            return false;
        }
		// 接住结果，回溯
        boolean left=hasPathSum(root.left,sum-root.val);
        boolean right=hasPathSum(root.right,sum-root.val);

        // 当前节点:
        // 左右为null才是叶子节点！
        if(root.left==null && root.right==null && root.val==sum){
        // 遍历到底，此时root值=sum 才返回true !
            return true; 
        }
        return left || right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21