バイナリツリーのパスの合計を計算する

Question

バイナリツリーのルートからリーフへのパスの合計を計算しようとしています。動作していないようですが、doesItの値はtrueになりますが、再帰的なので、スタックがポップするとfalseに戻ります。それを修正する方法がわからない。 どのようにしてdoItの値がtrueに変わるとスタック全体に伝播するようにコードを変更するのですか？ [5,4,8,11、NULL、NULL、NULL、7,2] 順序どおり

そう5は、二人の子供4及び8を有する4は1子11を有し、8：

ツリーを検討しますあなただけの子供にメソッドを呼び出すことで、指定した値を投げる子

hasPathSum（ルート、22）

public boolean hasPathSum(TreeNode root, int sum) { 
    boolean doesIt = false; 
    if (root != null) 
    { 
     doesIt = pathSum(root, sum, 0, doesIt); 
    } 
    return doesIt; 
} 

private static boolean pathSum(TreeNode root, int sum, int sumSoFar, boolean doesIt) 
{ 
    if (root.left == null && root.right == null) 
    { 
     if (sumSoFar+root.val == sum) 
     { 
      doesIt = true; 
      return doesIt; 
     } 
     return doesIt; 
    } 

    if (root.left != null) 
    { 
     pathSum(root.left, sum, sumSoFar+root.val,doesIt); 
    } 

    if (root.right != null) 
    { 
     pathSum(root.right, sum, sumSoFar+root.val,doesIt); 
    } 

    return doesIt; 
} 

Answer 1

を持っていません。私は少しこれにあなたのコードを書き換える：

private static boolean pathSum(TreeNode root, final int sum, int sumSoFar) { 
    if (root == null) return false; 
    if (root.left == null && root.right == null) return sumSoFar + root.val == sum; 
    return pathSum(root.left, sum, sumSoFar + root.val) || pathSum(root.right, sum, sumSoFar + root.val); 
} 

それは基本的な再帰です：nullノードの答えのために、葉は2つの分岐の1つで成功を達成しようとしている別のコーナーケース、一般的なケースの定義ではfalseです。

P.S.あなたが達成しようとしている質問とメソッドのシグネチャからはあまり明確ではありませんが、ルートから任意の葉までのパスがあるかどうかを確認すると仮定します。