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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!