LeetCode 112 Path Sum

LeetCode 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.

题目大意：

给定一个二叉树root和一个和sum，决定这个树是否存在一条从根到叶子的路径使得沿路所有节点的和等于给定的sum。

解题思路：

DFS搜索，二叉树的题。步骤主要是考虑

1. 空指针
2. 一个node情况或多个node情况（可合并）

注意事项：

1. 叶子节点是不含左儿子和右儿子

Java代码：

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

算法分析：

两种方法时间复杂度为O(n)，n为节点数。空间复杂度为O(h)，h为二叉树高度。

相关题目：

LeetCode 112 Path Sum
LeetCode 124 Binary Tree Maximum Path Sum