在 Python 中查找二叉树中第二个最深的结点的程序

在 Python 中查找二叉树中第二个最深的结点的程序

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

因此,如果输入如下所示:

在 Python 中查找二叉树中第二个最深的结点的程序

则输出将为1,因为第二深的结点是3。

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

  • 如果根为空,则
    • 返回null
  • nodes:=新列表
  • 将根插入 nodes 的末尾
  • 计数:= 0,上一个结点:= 0,现在结点:= 0
  • while 列表 nodes 不为空, do
    • new:=新列表
    • flag:= True
    • for each node in nodes, do
      • 如果 flag 为 true 并且(节点左侧为 null)并且(节点右侧为 null),则
      • prev:= now
      • now:= count
      • flag:= False
      • 如果节点的左侧不为 null,则
      • 将节点的左侧插入 new 的末尾
      • 如果节点右侧不为 null,则
      • 将节点的右侧插入 new 的末尾
    • nodes:= new
    • count:= count + 1
  • 返回 prev

为了更好地理解,请看以下实现:

例子

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程