バイナリツリーのモリストラバーサルでは、現在のノードに向かって接続を構築するために、すべての右の葉ノードを使用します。Morris traversal - リーフノードに到達したかどうかをチェックする方法?
葉ノードに到達すると、葉ノードを満たしているかどうかを判断するにはどうすればいいですか?
例えば、私たちは、チェックするために次の行を使用することはできません。 場合(ヌル== node.left & &ヌル== node.right)
ここnode.rightためモリスアルゴリズムの現在のノードを指しているので。
TreeNodeオブジェクトのフィールドを使用して、訪れたノードを常にマークすることができますが、多くの場合、このフィールドがないとどうなりますか?
葉ノードに到達したかどうかを確認する方法はありますか?ありがとう。
よろしく、 ジャック
は、あなたの答えをいただき、ありがとうございます。しかし、それは私の問題を解決しません。 – jack
事はジャックです、私の*解決策ではありませんでした。これが実生活でのやり方です。モリストラバーサルの全体のポイントは、再帰におけるスタック使用を避けることによってメモリを節約することです。あなたが提案したようにセットを持っているときは、平均的なO(logN)のスタックスペースを節約するためにO(N)のスペースを無駄にします。 –
ありがとうございましたShihab、私はあなたの答えを知らされていなかったので、私は遅く返信しています。はい、スペースの面では残念です。私の質問は、あらかじめ序列のトラバーサルを使用することを主張していることによるものです。私は郵便配達を使用している場合、解決することができます(あなたの答えのように?)、申し訳ありませんが、私はまだ試してみる時間がありませんでした。 – jack