매일 Leetcode 알고리즘-Path Sum-2019.01.13

중국어:

 ， ， 。

 ： 。

 ：

 sum = 22，

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

루트-엽 경로 5->4->11->2가 존재하기 때문에true로 돌아갑니다.
영어:
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
     / \
    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값과 새로운결점(방금 결점의 좌우 결점)을 방법에 전송하여 끊임없이 귀속시키고,
좌우 결점이 비어 있을 때까지 귀속됩니다.sum값이 마침 0인지 판단한다.

package cn.leetcode.easy;

import cn.kimtian.tree.TreeNode;

/**
 * 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.
 *
 * @author kimtian
 * @date 2019.01.13
 * @num 112
 */
public class PathSum {
    public boolean hasPathSum(TreeNode root, int sum) {
        // ， false
        if (root == null) {
            return false;
        }
        // ， 
        sum -= root.value;
        // ， ， ， 0
        if ((root.leftNode == null) && (root.rightNode == null)) {
            return (sum == 0);
        }
        // ， ， sum 
        return hasPathSum(root.leftNode, sum) || hasPathSum(root.rightNode, sum);
    }
}