Path Sum

Problem

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Recursive solution

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == sum; //We reach a leaf
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

Non-recursive solution using Stack

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false; //Always check null first 
        Stack<TreeNode> trees = new Stack<>();
        Stack<Integer> values = new Stack<>();
        trees.push(root);
        values.push(sum);
        while (!trees.isEmpty()) {
            TreeNode node = trees.pop();
            int value = values.pop();
            //We cannot use `return node.val == sum` here because we are not in recursion, the program will stops immediately 
            if (node.left == null && node.right == null && node.val == value) return true;
            if (node.left != null) {
                trees.push(node.left);
                values.push(value - node.val);
            }
            if (node.right != null) {
                trees.push(node.right);
                values.push(value - node.val);
            }
        }
        return false;
    }
}

Analysis

This is a typical tree traversal problem
The recursive solution is concise and easy to implement
We check whether we reach to a leaf, if so, we compare the node.val with current sum
Otherwise, we recursively check the left and right of current node

The non-recursive solution looks complicated but it might be asked in the interview with a higher chance
We need to have two Stack because we need to store the current sum
The idea is similar to the recursive solution

results matching ""

    No results matching ""