Pythonでの二分木ジグザグレベルの順序トラバーサル
二分木があるとしましょう。ジグザグレベルの順序トラバーサルを見つける必要があります。したがって、最初の行については、左から右にスキャンし、次に2番目の行から右から左にスキャンし、次に再び左から右にスキャンします。したがって、ツリーが次のような場合-
トラバーサルシーケンスは[[3]、[20,9]、[15,7]]
になりますこれを解決するには、次の手順に従います-
-
ツリーが空の場合は、空のリストを返します
-
queue:=キューを作成し、ルートをキューに挿入し、2つの空のリストresとres2を作成し、フラグをTrueに設定します
-
キューが空でない間
-
キューに存在するノードのリストを作成し、resに挿入します
-
キューに存在するノード値のリストを作成してから、res2に挿入します
-
フラグが設定されている場合、
-
i:=resの最後のサブリストの長さ– 1
-
i> =0
-
resの最後のサブリストのi番目の要素に正しいサブツリーがある場合、
-
右のサブツリーをキューに挿入します
-
-
resの最後のサブリストのi番目の要素がサブツリーを離れている場合、
-
左側のサブツリーをキューに挿入します
-
-
iを1減らします
-
-
-
それ以外の場合
-
i:=resの最後のサブリストの長さ– 1
-
i> =0
-
resの最後のサブリストのi番目の要素に正しいサブツリーがある場合、
-
右のサブツリーをキューに挿入します
-
-
resの最後のサブリストのi番目の要素がサブツリーを離れている場合、
-
左側のサブツリーをキューに挿入します
-
-
iを1減らします
-
-
-
-
res2を返す
理解を深めるために、次の実装を見てみましょう-
例
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def zigzagLevelOrder(self, root): if not root: return [] queue = [root] res = [] res2=[] flag = True while len(queue)!=0: res.append([i for i in queue]) res2.append([i.data for i in queue if i.data != 0]) queue = [] if flag: i=len(res[-1])-1 while i>=0: if res[-1][i].right: queue.append(res[-1][i].right) if res[-1][i].left: queue.append(res[-1][i].left) i-=1 else: i=len(res[-1])-1 while i>=0: if res[-1][i].left: queue.append(res[-1][i].left) if res[-1][i].right: queue.append(res[-1][i].right) i-=1 flag = not flag return res2 ob = Solution() tree = make_tree([3,9,20,None,None,15,7]) print(ob.zigzagLevelOrder(tree))
入力
[3,9,20,null,null,15,7]
出力
[[3], [20, 9], [15, 7]]
-
Pythonでの二分木の直径
二分木があるとしましょう。木の直径の長さを計算する必要があります。二分木の直径は、実際には、ツリー内の任意の2つのノード間の最長パスの長さです。このパスは必ずしもルートを通過する必要はありません。したがって、ツリーが以下のようになっている場合、パスの長さ[4,2,1,3]または[5,2,1,3]は3であるため、直径は3になります。 これを解決するには、次の手順に従います- dfsを使用して直径を見つけ、答えを設定します:=0 ルートdfs(root)を使用してdfs関数を呼び出します dfsは以下のdfs(node)のように機能します ノードが存在しない場合は、0を返します 左
-
Pythonで二分木を反転する
二分木があるとします。私たちの仕事は、逆二分木を作成することです。したがって、ツリーが以下のようになっている場合- 反転したツリーは次のようになります これを解決するために、再帰的アプローチを使用します ルートがnullの場合は、戻ります 左右のポインタを入れ替える 左のサブツリーと右のサブツリーを再帰的に解決します 例(Python) 理解を深めるために、次の実装を見てみましょう- class TreeNode: def __init__(self, data, left = None, right = None):