問題
2分木とゴール和が与えられたとき、ルートノードから木の葉ノードへのパスが存在し、そのパス上のすべてのノードの値を合計するとゴール和に等しくなるかどうかを判定しなさい。
説明: リーフノードとは、子を持たないノードのことです。
アイデア
自分で考えればいい
そんなことするつもりはありません。
........
....
ルート・ノードからリーフ・ノードへのパスは、深さ優先のトラバーサルを使うことを考えるのは簡単です。しかし、反復を使用してそれを行うことができます、また、ちょうどより多くのトラブル、ここでは直接問題を行うために再帰を使用します。
再帰的解法
三部作の始まり
- 最も重要なサブ問題が開始されます：上から下へのパスの合計が目標値である、それはルートノード、この値を控除し、それが最後に残っている値であるかどうかを判断するために、リーフノードまで、左と右のサブツリーを検証するように見ることができる、左と右のサブツリーはまた、個別にツリーで構成されるルートノードとして見ることができるので、このプロセスのツリー再帰。
ルートノードからリーフノードまでトラバースし、トラバースした各ノードをリーフノードまで合計します。再帰の場合も、左右の2つのパスがあり、トラバースした各ノードの値を引くだけです。各ノードの値を上から下に引いていき、リーフノードに到達し、残りの値がリーフノードと等しければ、条件を満たしたことになります。 - 戻り値：上記で記録された値とターゲットを比較した結果。
- 終了条件：リーフ・ノードでの再帰がなくなった、終了。
再帰コード
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null){
return false;
}
if(root.left == null && root.right == null){
//リーフノードに到達した。
return sum == root.val;
}
//左サブツリーと右サブツリーのいずれかが条件を満たすことができる。
return hasPathSum(root.left,sum - root.val) ||
hasPathSum(root.right,sum-root.val);
}
}
