二叉树最深层间隔最远结点

给定一棵非空二叉树，数据域值为不等于0的整数。请编写程序找出其最深层间隔最远的两个结点，输出这两个结点差的绝对值。如图1所示的各二叉树最深层间隔最远的结点为5和8。如果最深层只有一个结点，则输出0。

**输入格式:**

输入为一组用空格间隔的整数，个数不超过200个，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。

**输出格式:**

输出为一个整数，为二叉树最深层间隔最远的两个结点差的绝对值，如果最深层只有一个结点，则输出0。

**输入样例1:**

1 2 0 5 0 0 3 6 0 0 8 0 0

**输出样例1:**

3

**输入样例2:**

1 2 0 5 0 0 3 0 0

**输出样例2:**

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)。