7-322 二叉树最深间隔最远结点分数 10作者 朱允刚单位 吉林大学给定一棵非空二叉树数据域值为不等于0的整数。请编写程序找出其最深层间隔最远的两个结点输出这两个结点差的绝对值。如图1所示的各二叉树最深层间隔最远的结点为5和8。如果最深层只有一个结点则输出0。btreejpg输入格式输入为一组用空格间隔的整数个数不超过200个表示带空指针信息的二叉树先根序列其中空指针信息用0表示。输出格式输出为

思路：

1. 首先，根据输入的先根序列构建二叉树。
2. 然后，利用递归遍历二叉树，记录每个结点的深度。
3. 最后，找出最深层的两个结点，计算它们的差的绝对值。

具体实现如下：

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

def buildTree(nodes):
    if not nodes:
        return None
    val = nodes.pop(0)
    if val == 0:
        return None
    node = TreeNode(val)
    node.left = buildTree(nodes)
    node.right = buildTree(nodes)
    return node

def getDepth(node):
    if not node:
        return 0
    left_depth = getDepth(node.left)
    right_depth = getDepth(node.right)
    return max(left_depth, right_depth) + 1

def getDeepestNodes(node, depth, current_depth):
    if not node:
        return []
    if current_depth == depth:
        return [node]
    left_nodes = getDeepestNodes(node.left, depth, current_depth + 1)
    right_nodes = getDeepestNodes(node.right, depth, current_depth + 1)
    return left_nodes + right_nodes

def getDeepestNodesDifference(root):
    depth = getDepth(root)
    deepest_nodes = getDeepestNodes(root, depth, 1)
    if len(deepest_nodes) == 1:
        return 0
    return abs(deepest_nodes[0].val - deepest_nodes[1].val)

# 输入样例处理
input_str = input()
nodes = [int(x) for x in input_str.split()]
root = buildTree(nodes)

# 计算最深层间隔最远结点的差的绝对值
result = getDeepestNodesDifference(root)

# 输出结果
print(result)

复杂度分析：

• 构建二叉树的时间复杂度为O(n)，其中n为节点的个数。
• 计算最深层间隔最远结点的差的绝对值的时间复杂度为O(n)，其中n为节点的个数。
• 整体的时间复杂度为O(n)