バイナリツリートラバーサル（Python）

バイナリツリーをトラバースする###

#0 GitHub

https://github.com/Coxhuang/binary-tree-traversal

#1 周囲＃＃

Python3.7.3

#2 開始＃＃

#2.1 レベルトラバーサル###

#1 思考分析####

#2 コード＃＃＃＃

# Definition for a binary tree node.classTreeNode:"""
 ノード
    """
 def __init__(self, x):
  self.val = x
  self.left = None
  self.right = None
classSolution:
 def levelOrderBottom(self, root):"""
  レベルトラバーサル
  : param root:ルートノード
  : return: list_node -> List 
        """

  queue_node =[root]  #キュー
  list_node =[]  #結果リストを保存するための順序どおりのトラバーサル

  while queue_node:  #キューは空ではありません,ループし続ける

   node = queue_node.pop()  #チームを離れる
   if not node: #ノードが空です,ゼロから始めます,結果リストに空のノードを入れないでください
    continue
   list_node.append(node.val) #結果リストにノード値を保存します
   queue_node.insert(0, node.left) #左側のノードが最初にキューに入ります
   queue_node.insert(0, node.right) #適切なノードの後にチームに参加する

  print(list_node)return list_node

#3 テスト＃＃＃＃

出力

# レベルトラバーサル
[3,9,20,15,7]

#2.2 一次トラバーサル###

#1 アイデア####

#2 コード＃＃＃＃

# Definition for a binary tree node.classTreeNode:"""
 ノード
    """
 def __init__(self, x):
  self.val = x
  self.left = None
  self.right = None

classSolution:
 def levelOrderBottom(self, root):"""
  事前注文トラバーサル
  : param root:ルートノード
  : return: list_node -> List
        """
  stack_node =[root]  #スタック
  list_node =[]  #最初に結果ストレージリストをトラバースします

  while stack_node: #スタックは空ではありません
   node = stack_node.pop() #トップノードポップ
   if not node: #ノードが空です
    continue
   list_node.append(node.val) #空でないノード値をリストに保存します
   stack_node.append(node.right) #右側のノードが最初にスタックにプッシュされます
   stack_node.append(node.left) #左側のノードの後にスタックをプッシュします
  print(list_node)return list_node
    
 def preOrderBottom_re(self, root):"""
  トラバーサル再帰の事前注文
  : param root:ルートノード
  : return: list_node -> List
        """
        
  if not root:return None
  print(root.val)
  self.preOrderBottom_re(root.left)
  self.preOrderBottom_re(root.right)

#3 テスト＃＃＃＃

#2.3 インオーダートラバーサル###

#1 アイデア####

#2 コード＃＃＃＃

# Definition for a binary tree node.classTreeNode:"""
 ノード
    """
 def __init__(self, x):
  self.val = x
  self.left = None
  self.right = None

classSolution:
 def levelOrderBottom(self, root):"""
  インオーダートラバーサル非再帰的
  : param root:ルートノード
  : return: list_node -> List
        """
  stack_node =[]  #スタック
  list_node =[]  #インオーダートラバーサル結果ストレージリスト
  node_p = root #現在のノード
  while stack_node or node_p: #現在のノードが空でないか、スタックが空ではありません

   while node_p: #左端まで移動します
    stack_node.append(node_p) #ノードプッシュ
    node_p = node_p.left #ポインタが残っています

   node = stack_node.pop() #スタックを解除する
   list_node.append(node.val) #ノードデータを取得する
   node_p = node.right #ノードを取得
  print(list_node)return list_node
    
 def inOrderBottom_re(self, root):"""
  順序どおりのトラバーサル再帰
  : param root:ルートノード
  : return: list_node -> List
        """

  if not root:return None
  self.inOrderBottom_re(root.left)print(root.val)
  self.inOrderBottom_re(root.right)

#3 テスト＃＃＃＃

#2.4 注文後のトラバーサル###

#1 アイデア####

#2 コード＃＃＃＃

# Definition for a binary tree node.classTreeNode:"""
 ノード
    """
 def __init__(self, x):
  self.val = x
  self.left = None
  self.right = None

classSolution:
 def levelOrderBottom(self, root):"""
  注文後のトラバーサル非再帰的
  : param root:ルートノード
  : return: list_node -> List
        """
  stack_node =[root]
  list_node =[]while stack_node:
   node = stack_node.pop()if node.left: #左の子供は空ではありません
    stack_node.append(node.left) #左の子供がスタックを押す
   if node.right: #右の子は空ではありません
    stack_node.append(node.right) #右子プッシュ

   list_node.append(node.val) #現在のポインタ値を取得します

  list_node.reverse() #ネゲート
  return list_node
    
 def postOrderBottom_re(self, root):"""
  注文後のトラバーサル再帰
  : param root:ルートノード
  : return: list_node -> List
        """

  if not root:return None
  self.postOrderBottom_re(root.left)
  self.postOrderBottom_re(root.right)print(root.val)

#3 テスト＃＃＃＃