欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode ---- 112、路径总和

程序员文章站 2022-05-20 16:13:29
...

题目链接

思路:

遍历时,分别遍历每一个节点的左右子树。遍历到每一个节点,用剩余的和减去当前节点的值,接着继续向下遍历其左右子树,直到遍历到叶子节点时,判断此时剩余和减去叶节点值是否为0,若为0,则说明存在这样一条路径。

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum - root.val == 0;
        }
        return hasPathSum(root.left, sum - root.val) || 
                hasPathSum(root.right, sum - root.val);
    }
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

 

相关标签: LeetCode