LeetCode 112. Path Sum

解法一 Recursive

思路

我们要找到到达叶子节点时，该路径的值是否等于sum。同时，还要检查左子树和右子树是否有这样的值。只要有，就可以返回true。

代码

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        sum -= root.val; // 对每一层的节点，sum 相应减少
        if (root.left == null && root.right == null) {
            return sum == 0; // 到叶子节点时，检查 sum 是否为0
        }

        // 只要左子树和右子树有至少一组解即可
        return hasPathSum(root.left) || hasPathSum(root.right);
    }
}

复杂度分析

• 时间复杂度
  • O(N)
• 空间复杂度
  • O(H) – 取决于树的高度

解法二 Iteration

思路

利用两个栈，储存每一层节点的值和对应的剩余 sum 值。到叶子节点时，sum 的值如果出现 0，那么这个路径有解。

代码

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;

        Stack<TreeNode> tree_stack = new Stack<>();
        Stack<Integer> sum_stack = new Stack<>();
        tree_stack.push(root);
        sum_stack.push(sum - root.val);
        while (!tree_stack.isEmpty()) {
            TreeNode node = tree_stack.pop();
            int curr_sum = sum_stack.pop();

            if (node.left == null && node.right == null && curr_sum == 0) {
            return true;
            }

            if (node.left != null) {
                tree_stack.push(node.left);
                sum_stack.push(curr_sum - node.left.val);
            }

            if (node.right != null) {
                tree_stack.push(node.right);
                sum_stack.push(curr_sum - node.right.val);
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度
  • O(n) 遍历了所有节点
• 空间复杂度
  • O(H)

Takeaway

本作品采用《CC 协议》，转载必须注明作者和本文链接