112|112 Path Sum 112PathSum

title: Path Sum
tags:
- path-sum
- No.112
- simple
- tree
- recursive
Description 【112|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.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,

5 / \ 48 // \ 11134 /\\ 721

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

empty tree

Solutions Recursively reduce the value of the current node from sum. The running time is the same as BFS, O(V):

/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) {return false; } return f(root, sum); }private boolean f(TreeNode x, int s) { if (x.left == null && x.right == null && x.val == s) {return true; }boolean fl = false; boolean fr = false; if (x.left!= null) {fl = f(x.left,s - x.val); } if (x.right != null) {fr = f(x.right, s - x.val); } return fl || fr; } }