メソッドがスタック内でどのように形成され、メソッドの戻り値がメソッド内で2回繰り返される場合

Question

バイナリツリーの再帰的なinorder、preorder、postoreder traversalのスタックを作成しようとしました。例えば、テストケースのために私の答えが「本当」であるべき、のような他の例では、say.And、例えば、

boolean method(root) 
{ 
    // more code 
    method(root.left()); 
    method(root.right()); 
} 

、どこかで、メソッドの呼び出し（root.leftは（））がfalseを返しますメソッドの呼び出し（root.right（））はtrueを返します。これは私たちの答えになります。しかし、メソッドの呼び出し（root.left（））が最初にどこかで完了しているので、実行の間にfalseを返している可能性があります。メソッド（root.right（））から結果を真にするにはどうすればいいですか？私はスタックがどのように形成され、メソッドからの値がこのように再帰呼び出しが起こったときに返されると考えています。私が間違っていればそれを解明してください。

Answer 1

値を返す必要があります。このメソッドは、ロジック内で返された値を使用して検索を停止/継続する必要があります。

ベースケースでtrueをfalseに戻す必要があります。次に、最初の再帰呼び出しを行うときに、結果が真であれば最初の再帰呼び出しを行うだけです。 2番目の再帰呼び出しは、必要に応じてメソッドの結果になります。私は最後のより読みが、初心者にはより詳細を見つけるかもしれない見つける

boolean method(root) 
{ 
    return root != null && (root.value == someValue || 
          method(root.left()) || 
          method(root.right())); 
} 

：

boolean method(root) 
{ 
    if(root == null) { // base case 1 
    return false; 
    } 
    if(root.value == someValue) { // base case 2, what should be a positive 
    return true; 
    } 
    // default search left first and return true if true 
    if(method(root.left())) { 
    return true; 
    } 
    // default search right and return true if true 
    if(method(root.right())){ 
    return true; 
    } 
    // return false since neither recursive calls were true 
    return false; 
} 

これは非常に冗長で、代わりに次のように書くことができます。したがって、あなたはこのような何かを見ています最初の方がはっきりしています。

呼び出し元が最初の再帰呼び出しの後で操作を再開すると（呼び出しの共有も同じであった可能性があります）、必要に応じてロジックが継続され、右側が再帰します。

システムスタックを気にしないでください。ベースケースを気にしてテストしてください。次に、再帰呼び出しで問題が小さくなるのを見るために、デフォルトのケースを行うために複雑さを加えるのが最も簡単です。非常に深い再帰的ラウンドで何が起きているのかを見て、大きな木を起点にしてこのことを考えてみるよりも、シンプルなものからより複雑なものに進む方がはるかに良いです。