Python程序检查二叉树中所有叶子节点是否都在同一层

假设我们有一个二叉树，我们需要检查所有叶子节点是否都在同一层。

所以，如果输入类似于

那么输出将为 True

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

  • 定义一个函数 dfs()。它将接收根节点和深度 d 作为参数。

  • 如果根节点不为空，则

    • 如果根节点的左子节点和右子节点都为空，则

      • 将 d 添加到 depth 列表的末尾。

    • 否则，

      • dfs(根节点的左子节点, d + 1)

      • dfs(根节点的右子节点, d + 1)

  • 在主方法中，执行以下操作：

  • depth := 一个新的列表

  • dfs(根节点, 0)

  • 当 depth 列表中只有一个值时返回 true。

让我们看一下下面的实现，以便更好地理解：

示例

 在线演示

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None

class Solution:
   def solve(self, root):
      self.depth = []
      self.dfs(root, 0)
      return len(set(self.depth)) == 1
   def dfs(self, root, depth):
      if root:
         if not root.left and not root.right:
            self.depth.append(depth)
         else:
            self.dfs(root.left, depth + 1)
            self.dfs(root.right, depth + 1)
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.left.left = TreeNode(2)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
print(ob.solve(root))

输入

root = TreeNode(5)
root.left = TreeNode(4)
root.left.left = TreeNode(2)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)

输出

True

更新于: 2020年10月10日

131 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告