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

To recursively traverse a binary tree and check if there is a path from root to leaf node with a given sum, pass the current node and the remaining sum as parameters to the recursive function.

If the input node is null, return false. If it’s a leaf node, check if the remaining sum is equal to the value of the node. If they are equal, return true, otherwise false. This is also the base case for recursion.

For non-leaf nodes, recursively call the function on both its left and right children, using the logical or operator || to combine the results. If either call returns true, the function should return true. During recursion, subtract the value of the current node from the remaining sum passed to the child nodes.

Code

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);
	    }
	}
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return dfs(root, targetSum);
    }

    private boolean dfs(TreeNode root, int s) {
        if (root == null) {
            return false;
        }
        s -= root.val;
        if (root.left == null && root.right == null && s == 0) {
            return true;
        }
        return dfs(root.left, s) || dfs(root.right, s);
    }
}

// OJ: https://leetcode.com/problems/path-sum/
// Time: O(N)
// Space: O(H)
class Solution {
public:
    bool hasPathSum(TreeNode* root, int target) {
        if (!root) return false;
        if (!root->left && !root->right) return target == root->val;
        return hasPathSum(root->left, target - root->val) || hasPathSum(root->right, target - root->val);
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def dfs(root, s):
            if root is None:
                return False
            s += root.val
            if root.left is None and root.right is None and s == targetSum:
                return True
            return dfs(root.left, s) or dfs(root.right, s)

        return dfs(root, 0)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque


class Solution(object):
  def hasPathSum(self, root, sum):
    """
    :type root: TreeNode
    :type sum: int
    :rtype: bool
    """
    if root:
      queue = deque([(root, root.val)])
      while queue:
        p, s = queue.popleft()
        left, right = p.left, p.right
        if left:
          queue.append((p.left, s + p.left.val))
        if right:
          queue.append((p.right, s + p.right.val))
        if not left and not right and s == sum:
          return True
      return False
    return False

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
	var dfs func(*TreeNode, int) bool
	dfs = func(root *TreeNode, s int) bool {
		if root == nil {
			return false
		}
		s += root.Val
		if root.Left == nil && root.Right == nil && s == targetSum {
			return true
		}
		return dfs(root.Left, s) || dfs(root.Right, s)
	}
	return dfs(root, 0)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (root == null) {
        return false;
    }
    const { val, left, right } = root;
    if (left == null && right == null) {
        return targetSum - val === 0;
    }
    return (
        hasPathSum(left, targetSum - val) || hasPathSum(right, targetSum - val)
    );
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
    function dfs(root, s) {
        if (!root) return false;
        s += root.val;
        if (!root.left && !root.right && s == targetSum) return true;
        return dfs(root.left, s) || dfs(root.right, s);
    }
    return dfs(root, 0);
};

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
        match root {
            None => false,
            Some(node) => {
                let mut node = node.borrow_mut();
                // 确定叶结点身份
                if node.left.is_none() && node.right.is_none() {
                    return target_sum - node.val == 0;
                }
                let val = node.val;
                Self::has_path_sum(node.left.take(), target_sum - val)
                    || Self::has_path_sum(node.right.take(), target_sum - val)
            }
        }
    }
}

112 - Path Sum

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions