Pythonの方向のリストを使用してバイナリツリーをトラバースするプログラム

二分木があり、「R」（右）、「L」（左）、「U」（上）で構成される文字列のリストが移動するとします。ルートから開始して、次の移動で各移動を実行することにより、ツリーをトラバースする必要があります。「R」は、右の子へのトラバースを示します。 「L」は、左の子へのトラバースを示します。 「U」は、その親へのトラバースを示します。

したがって、入力が次のような場合

["R"、 "R"、 "U"、 "L"]の場合、出力は3になります

これを解決するには、次の手順に従います-

• 過去：=新しいリスト

• 移動の移動ごとに、実行します

  • 過去の終わりにルートを挿入

  • 移動が「L」と同じ場合、

    • ルート：=ルートの左側

  • それ以外の場合、移動が「R」と同じ場合、

    • ルート：=ルートの右

  • それ以外の場合

    • 過去から最後の要素を削除する

    • ルート：=過去の最後の要素と過去の要素を削除

• ルートの戻り値

理解を深めるために、次の実装を見てみましょう-

例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, moves):
      past = []
      for move in moves:
         past.append(root)
         if move == "L":
            root = root.left
         elif move == "R":
            root = root.right
         else:
            past.pop()
            root = past.pop()
      return root.val
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
traverse = ["R","R","U","L"]
print(ob.solve(root, traverse))

入力

root = TreeNode(2) root.right = TreeNode(4) root.right.left =
TreeNode(3) root.right.right = TreeNode(5) ["R","R","U","L"]

出力

3