BST、PythonのInorderトラバーサルの論理を理解する

Question

私はインタビューをコーディングし、さまざまなデータ構造を扱うために勉強しています。

私はツリーの問題に比較的新しいので、毎日問題を練習しています。

メモリにコミットされた数式を持つことと、真にそれらを理解するもう1つの方法です。私が何かを理解すると、より困難な問題にその理解を適用するのは簡単です。

再帰的なソリューションは精神的に視覚化するのが少し難しく、直感的には意味をなさないものの、スタック上で何が起こっているのかを深く理解しようとしています。

私は木を持ち、トラバーサルのためにしたいと思っています。問題ない。

data = [] 

def checkBST(root): 
    if root: 
     checkBST(root.left) 
     data.append(root.data) 
     checkBST(root.right) 
    print(data) 

Iメソッドを通過するものそれぞれに格納されている印刷するデータ変数を作成しました。

それは私が論理的に何が起こっているかを見て、私のロジックが正しいかどうかを知りたいしようとしています

[] 
[1] 
[1] 
[1, 2] 
[1, 2, 3] 
[1, 2, 3] 
[1, 2, 3] 
[1, 2, 3, 4] 
[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5, 6] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 

を印刷。

15の印刷結果と7つのノードがあります。ノードがNoneであるノードが8つ確認されているため、15になります。ノード1、3、5、7で発生します。

右側のツリーの左半分をチェックしています。

[] 
#nothing stored because we move onto Node 2 as we don't hit the base case. 
[1] 
#1 stored because Node 1 doesn't have a left value. So we move onto the append call. 
[1] 
#1 returned because Node 1 doesn't have a right value. 
[1, 2] 
#2 stored because because we finished checking the left side and moved onto append data. 
[1, 2, 3] 
#3 is stored because we are calling the in order traversal on the right side of two now. 
[1, 2, 3] 
#3 is returned again because it doesn't have a root.left 
[1, 2, 3] 
#3 is returned again because it doesn't have a root.right 
[1, 2, 3, 4] 
# we hit the append method for 4, now we move onto the in order traversal on the right 
[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5] 
[1, 2, 3, 4, 5, 6] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 2, 3, 4, 5, 6, 7] 

右側が左側と同じようにチェックされるので、論理が冗長になると書いていません。

正しい形式でこの問題を検討している場合は、明確にしたいだけです。

ご理解いただきありがとうございます！

Answer 1

出力のコメントが必ずしも正しいとは限りません。

最初の出力（[]）は、関数呼び出しが終了すると発生します。これが起きる最初の呼び出しは、rootがノード1であり、そこから最初の再帰呼び出しが行われたときです。その呼び出しはNoneを引数とするため、呼び出しがprintステートメントに達するのは初めてです。

は、だから我々は、これらの継続的な呼び出しを持っている：

checkBST(4) 
    checkBST(2) # left child of 4 
     checkBST(1) # left child of 2 
      checkBST(None) # left child of 1 
       print # --> [] 

その最深のコールが終了すると、ノード1との機能は、データリストに1を追加し、次に右の子のための再帰呼び出しを行いますもいますNoneおよび[1]が印刷されます。

これはプロセスの可視化です。列は再帰の深さを表し、行は時間が進むにつれてイベントのシーケンスを表します（下向き）。最後の列は、dataの現在の値を示すために予約されています。黄色の背景がある場合は、印刷されていることを意味します。

淡い青色は、コードがその再帰深度で実行されることを意味します。暗い青は対応する関数呼び出しが（スタック上で）保留中であり、ネストされた再帰呼び出しが戻るのを待っていることを意味します。

同じ出力が時々繰り返される理由をも見ることができ、このイメージから：アルゴリズムがバックトラッキングされるように、異なる再帰レベルで印刷されます。