导航
导航
文章目录
  1. 题目
  2. 翻译

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.

翻译

给出一颗二叉树和一个sum,判断树上是否有一个从根到叶子节点的路径,使得该路径上所有的值相加等于给出的sum。
例如:
给出以下树,和sum=22,
     5
    /  \
   4    8
  / \   / \
 11    13  4
 / \        \
7   2       1
返回true,因为有一条从根到叶子节点的路径 5->4->11->2,其和为22。

简单遍历即可,当树为空树时返回false,当根节点左右孩子都是空或叶子节点时,判断其值是否与给出的值相等。其他节点用sum减去该节点的值,递归判断:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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;

int diff = sum - root.val;
return hasPathSum(root.left, diff) || hasPathSum(root.right, diff);

}
}