0

これは問題の説明です：

「ツリーと合計が与えられた場合、ルートからリーフへのパスがあり、パスに沿ったすべての値を合計すると、指定された合計に等しくなる場合は、trueを返します。」

私はそれを次のように実装しました：

int hasPathSum(Node* node, int sum) {
    if(node == NULL)
        return sum == 0;

    int diff = sum - node->data;

    if(diff < 0) return 0;

    if(diff == 0)
        return node->left == NULL && node->right == NULL ? 1 : 0;

    if(diff < node->data)
        return hasPathSum(node->left, diff);
    else
        return hasPathSum(node->right, diff);
}

の違いに応じて、1つのサブツリーのみをトラバースし、両方はトラバースしません(sum - node->data)。

ただし、推奨されるソリューションでは、次のように両方のサブツリーをトラバースする必要がありました。

int hasPathSum(Node* node, int sum) { 
  // return true if we run out of tree and sum==0 
  if (node == NULL) { 
    return(sum == 0); 
  } 
  else { 
  // otherwise check both subtrees 
    int subSum = sum - node->data; 
    return(hasPathSum(node->left, subSum) || 
           hasPathSum(node->right, subSum)); 
  } 
}

なぜ両方のサブツリーをトラバースする必要があるのか​​わかりませんか？

問題の原因は次のとおりです。問題7

編集：

ツリーがBSTであるという私の側の悪い仮定。その単なる二分木。

ただし、それがBSTの場合、実装に関するフィードバックを聞きたいですか？他の解決策よりも、私がやった方法でそれを行う方が良いのではないでしょうか？（このソリューションは任意の二分木用であるため、比較するのは少し不公平です）

ソリューションの編集：

私の提案した解決策の問題を説明するanatolygの応答をここで参照してください。anatolygに感謝します。

4

4 に答える 4

2

あなたの問題の声明は、ツリーがどのように配置されているかについて何も言及していないので、あなたの左/右のテストが何をしようとしているのか理解できません。node->leftまたはnode->rightサブツリーの内容については、テストせずに知ることはできません。

また、提案されたソリューションで||は、左側のサブツリーが一致すると短絡するため、必ずしも両方のサブツリーをトラバースする必要はありません。パスがない場合にのみツリー全体をトラバースします。パスがないことを確認するために、明らかにすべてのパスをテストする必要があります。（OK、最終パスで一致するものが見つかった場合は、ツリー全体をトラバースします...）

于 2012-08-14T18:52:04.877 に答える
2

二分探索木のノードの特別な配置は、合計ではなく、数値の検索にのみ役立ちます。深さが100のような非常に大きな木で、左側のすべてのノードに沿って求められているパスがあり、ターゲットの合計が適度に大きい（たとえば、1 + 2 + 3 + ... + 100）と想像してください。

アルゴリズムがルートから開始すると、diffは大きくなり、ツリーの右側のブランチに移動します。ここで、合計は必ずしも存在しません（たとえば、すべての要素が1000000000より大きいため、大きすぎます）。

于 2012-08-14T19:01:48.720 に答える
1

データ1を含むルートノードを持つ二分木を考えます。ルートノードには2つのサブツリーがあり、左側には2があり、右側には3があります。ノード2の左側のサブツリーは5です。

ルート全体からリーフノードへのパスの合計が8になるかどうかを尋ねると、答えは「はい」です。

全体のルート=1、左のサブツリー= 2、左のサブツリー= 5、合計は8になります。ただし、どちらのパスが正しい合計になるかは事前にわからないため、両方のサブツリーを下に移動する必要があります。再帰的に。

二分木コードは短くする必要があります。二分木の再帰的な性質と、ツリーがnullであるか、左右のサブツリーがあるという事実を使用します。

于 2012-08-14T19:03:13.000 に答える
0

ツリーは検索ツリーではないため、父親のデータからの子供のデータについては何もわかりません。

于 2012-08-14T18:53:31.167 に答える