매일 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);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
38. Java의 Leetcode 솔루션텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
