【LeetCode-面接アルゴリズムクラシック-Java実装】【112-Path Sum(パスと)】
【112-Path Sum(経路と)】
【LeetCode-面接アルゴリズムクラシック-Java実装】【すべてのテーマディレクトリインデックス】
原題
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,
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
テーマの大意
1本の二叉木と1つの和を与え、木の根の結点から葉の結点までのすべての結点の和が与えられた和に等しいかどうかを判断し、等しい場合はtrueを返し、そうでない場合はfalseを返す.
問題を解く構想.
ツリーを遍歴し,遡及法を用いて解く.
コード実装
ツリーノードクラス
アルゴリズム実装クラス
評価結果
画像をクリックすると、マウスは解放されず、位置をドラッグして、解放された後、新しいウィンドウで完全な画像を表示します.
特別説明
転載を歓迎します.転載は出典を明記してください.http://blog.csdn.net/derrantcm/article/details/47414069】
【LeetCode-面接アルゴリズムクラシック-Java実装】【すべてのテーマディレクトリインデックス】
原題
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.
テーマの大意
1本の二叉木と1つの和を与え、木の根の結点から葉の結点までのすべての結点の和が与えられた和に等しいかどうかを判断し、等しい場合はtrueを返し、そうでない場合はfalseを返す.
問題を解く構想.
ツリーを遍歴し,遡及法を用いて解く.
コード実装
ツリーノードクラス
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
アルゴリズム実装クラス
public class Solution {
private boolean stop = false; //
public boolean hasPathSum(TreeNode root, int sum) {
calculate(root, 0, sum);
return stop;
}
/** * * @param node * @param cur * @param sum */
private void calculate(TreeNode node, int cur, int sum) {
if (!stop && node != null) { // ,
// , sum, , stop
if (node.left == null && node.right == null && (node.val + cur == sum) ) {
stop = true;
}
// ,
if (node.left != null) {
calculate(node.left, cur + node.val, sum);
}
if (node.right != null) {
calculate(node.right, cur + node.val, sum);
}
}
}
}
評価結果
画像をクリックすると、マウスは解放されず、位置をドラッグして、解放された後、新しいウィンドウで完全な画像を表示します.
特別説明
転載を歓迎します.転載は出典を明記してください.http://blog.csdn.net/derrantcm/article/details/47414069】