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

更新于: 2020年10月21日

225 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告