Python 程序检查树的中序遍历序列是否为回文

假设我们有一棵二叉树，其中每个节点包含一个 0-9 的数字，我们需要检查其中序遍历是否为回文。

因此，如果输入类似于

则输出将为 True，因为其中序遍历为 [2,6,10,6,2]。

为了解决这个问题，我们将遵循以下步骤 -

  • 如果根节点为空，则
    • 返回 True
  • stack := 新栈
  • curr := 根节点
  • inorder := 新列表
  • 当栈不为空或 curr 不为空时，执行以下操作
    • 当 curr 不为空时，执行以下操作
      • 将 curr 推入栈
      • curr := curr 的左节点
    • node := 从栈中弹出的元素
    • 将 node 的值插入 inorder 列表末尾
    • curr := node 的右节点
  • 当 inorder 与 inorder 的逆序相同则返回 true，否则返回 false。

让我们看看以下实现以获得更好的理解 -

示例

 在线演示

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):
      if not root:
         return True
      stack = []
      curr = root
      inorder = []
      while stack or curr:
         while curr:
            stack.append(curr)
            curr = curr.left
         node = stack.pop() inorder.append(node.val)
         curr = node.right
      return inorder == inorder[::-1]
ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

输入

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

输出

True

更新于: 2020年10月20日

197 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告