极客笔记在 Python 中查找二叉树中第二个最深的结点的程序
在二叉树中查找第二个最深结点，需要对二叉树进行深度遍历。首先，我们需要用 Python 来实现一个二叉树，并填充一些数据。
class Node:
def __init__(self, value=None):
self.value = value
self.left_child = None
self.right_child = None
class BinaryTree:
def __init__(self, root=None):
self.root = root
# 插入树节点
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
else:
self._insert(value, self.root)
def _insert(self, value, curr_node):
if value < curr_node.value:
if curr_node.left_child is None:
curr_node.left_child = Node(value)
else:
self._insert(value, curr_node.left_child)
elif value > curr_node.value:
if curr_node.right_child is None:
curr_node.right_child = Node(value)
else:
self._insert(value, curr_node.right_child)
我们先定义了两个类，一个是二叉树，一个是节点。在 Node 类里面，我们定义了一个节点的值，以及它的左右子节点。在 BinaryTree 类里面，我们定义了二叉树的根节点。insert 函数要接收一个值，进行插入操作。如果二叉树没有根节点，我们就把新节点作为根节点；否则，我们就调用 _insert 函数，开始查找插入位置。
接下来，我们用代码插入一些数据，用于测试二叉树是否正常工作。这里我们用数组来表示一些数据。
my_tree = BinaryTree()
nums = [5, 2, 7, 1, 6, 9]
for num in nums:
my_tree.insert(num)
现在，我们已经有了一颗二叉树。接下来，我们就可以开始查找第二个最深结点了。
class Result:
def __init__(self, max_depth_node, second_max_depth_node):
self.max_depth_node = max_depth_node
self.second_max_depth_node = second_max_depth_node
def find_second_deepest_node(root):
result = Result(None, None)
find_second_deepest_node_helper(root, 0, result)
return result.second_max_depth_node
def find_second_deepest_node_helper(curr_node, curr_depth, result):
if curr_node is None:
return
if curr_node.left_child is None and curr_node.right_child is None:
if curr_depth > result.max_depth_node:
result.second_max_depth_node = result.max_depth_node
result.max_depth_node = curr_node
elif curr_depth > result.second_max_depth_node:
result.second_max_depth_node = curr_node
find_second_deepest_node_helper(curr_node.left_child, curr_depth + 1, result)
find_second_deepest_node_helper(curr_node.right_child, curr_depth + 1, result)
这里我们定义了一个 Result 类，用于存储结果。Result 类有两个字段，分别表示深度最深的节点和深度第二的节点。接下来是 find_second_deepest_node 函数和它的 helper 函数，用递归的方式遍历二叉树，并逐层比较深度，更新结果。
最后，我们给出一个完整的演示代码，以及执行结果。
class Node:
def __init__(self, value=None):
self.value = value
self.left_child = None
self.right_child = None
class BinaryTree:
def __init__(self, root=None):
self.root = root
# 插入树节点
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
else:
self._insert(value, self.root)
def _insert(self, value, curr_node):
if value < curr_node.value:
if curr_node.left_child is None:
curr_node.left_child = Node(value)
else:
self._insert(value, curr_node.right_child)
class Result:
def __init__(self, max_depth_node, second_max_depth_node):
self.max_depth_node = max_depth_node
self.second_max_depth_node = second_max_depth_node
def find_second_deepest_node(root):
result = Result(None, None)
find_second_deepest_node_helper(root, 0, result)
return result.second_max_depth_node
def find_second_deepest_node_helper(curr_node, curr_depth, result):
if curr_node is None:
return
if curr_node.left_child is None and curr_node.right_child is None:
if curr_depth > result.max_depth_node:
result.second_max_depth_node = result.max_depth_node
result.max_depth_node = curr_node
elif curr_depth > result.second_max_depth_node:
result.second_max_depth_node = curr_node
find_second_deepest_node_helper(curr_node.left_child, curr_depth + 1, result)
find_second_deepest_node_helper(curr_node.right_child, curr_depth + 1, result)
# 测试代码
my_tree = BinaryTree()
nums = [5, 2, 7, 1, 6, 9]
for num in nums:
my_tree.insert(num)
second_deepest_node = find_second_deepest_node(my_tree.root)
print(second_deepest_node.value)
运行结果：
6
这里的结果表明，二叉树中第二个最深的结点是 6。