Question

Formatted question description: https://leetcode.ca/all/112.html

112	Path Sum

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.

@tag-tree

Algorithm

Use recursion to constantly find the left and right child nodes of the child node, and the parameters of calling the recursive function are only the current node and the sum value.

First of all, if the input is an empty node, it will directly return false. If the input is only one root node, compare the value of the current root node and the parameter sum if the value is the same. If they are the same, return true, otherwise false. This condition is also the termination condition of recursion.

The next step is to start recursion. Since the return value of the function is True/False, you can recurse in both directions at the same time, using or || in the middle to connect. As long as one of them is True, the whole result is True. When recursing left and right nodes, the sum value at this time should be the original sum value minus the value of the current node.

Code

Java

public class Path_Sum {

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */
	public class Solution_substract {
	    public boolean hasPathSum(TreeNode root, int sum) {

	        if (root == null) {
	            return false;
            }

	        if (root.left == null && root.right == null && root.val == sum) {
	            return true;
            }

	        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
	    }
	}

	public class Solution_add {
	    public boolean hasPathSum(TreeNode root, int target) {

	        if (root == null) {
	            return false;
	        }
	        return hasPathSum(root, target, 0);
	    }

	    public boolean hasPathSum(TreeNode root, int target, int sum) {

            if (root == null) {
                return false;
            }

            // below if-s are mainly for checking root node, since it must be root-to-left, not root itself
            if (root.left == null && root.right == null) {
                return sum + root.val == target;
            }

            return hasPathSum(root.left, target, sum + root.val)
                || hasPathSum(root.right, target, sum + root.val);
	    }
	}
}

All Problems

All Solutions