Python程式：使用方向列表遍歷二叉樹

假設我們有一棵二叉樹和一個字串列表moves，其中包含“R”（右）、“L”（左）和“U”（上）。從根節點開始，我們必須透過執行moves中的每個操作來遍歷樹，其中： “R”表示遍歷到右子節點。 “L”表示遍歷到左子節點。 “U”表示遍歷到其父節點。

因此，如果輸入類似於

["R","R","U","L"]，則輸出將為3

為了解決這個問題，我們將遵循以下步驟：

• past := 新列表

• 對於moves中的每個操作，執行以下操作：

  • 在past的末尾插入根節點

  • 如果操作與“L”相同，則

    • root := root的左節點

  • 否則，如果操作與“R”相同，則

    • root := root的右節點

  • 否則，

    • 從past中刪除最後一個元素

    • root := past中的最後一個元素，並將其從past中刪除

• 返回root的值

讓我們看看以下實現，以便更好地理解：

示例

 即時演示

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

Arnab Chakraborty

更新於: 2020年10月21日

225 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習