Python程序：查找二叉树中次深节点

假设我们有一个二叉树；我们需要找到次深叶节点的深度。如果有多个最深叶节点，则次深叶节点将是次高的节点。我们知道根节点的深度为0。

因此，如果输入如下所示：

则输出将为1，因为次深节点为3。

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

  • 如果根节点为空，则
    • 返回空
  • 节点 := 一个新的列表
  • 将根节点插入节点列表的末尾
  • 计数 := 0，前 := 0，现 := 0
  • 当节点列表不为空时，执行以下操作：
    • 新建 := 一个新的列表
    • 标志 := True
    • 对于节点列表中的每个节点，执行以下操作：
      • 如果标志为真且（节点的左子节点为空）且（节点的右子节点为空），则
        • 前 := 现
        • 现 := 计数
        • 标志 := False
      • 如果节点的左子节点不为空，则
        • 将节点的左子节点插入新建列表的末尾
      • 如果节点的右子节点不为空，则
        • 将节点的右子节点插入新建列表的末尾
    • 节点 := 新建
    • 计数 := 计数 + 1
  • 返回前

让我们看看下面的实现来更好地理解

示例

在线演示

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

class Solution:
   def solve(self, root):
      if root is None:
         return None
      nodes = []
      nodes.append(root)
      count = 0
      prev = 0
      now = 0
      while nodes:
         new = []
         flag = True
         for node in nodes:
         if flag and (not node.left) and (not node.right):
            prev = now
            now = count
            flag = False
         if node.left:
            new.append(node.left)
         if node.right:
            new.append(node.right)
      nodes = new
      count += 1
   return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

输入

root = TreeNode(2)
root.left = TreeNode(3)

root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)

root.right.right.right = TreeNode(8)

输出

1

更新于：2020年11月26日

258 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告