57 二叉树的下一个结点

题目描述

给定一棵二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点。

解题思路

核心思想：根据二叉树的结构分析。

关键步骤：

1. 如果节点有右子树，下一个节点是右子树的最左节点
2. 如果节点没有右子树，是父节点的左子节点，下一个节点是父节点
3. 如果节点没有右子树，是父节点的右子节点，向上遍历找到第一个是左子节点的节点

Python 实现

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


def get_next(node):
    """
    找出中序遍历的下一个节点

    Args:
        node: 当前节点

    Returns:
        TreeNode: 下一个节点
    """
    if not node:
        return None

    # 有右子树
    if node.right:
        node = node.right
        while node.left:
            node = node.left
        return node

    # 没有右子树，是父节点的左子节点
    while node.parent:
        if node.parent.left == node:
            return node.parent
        node = node.parent

    return None


# 测试代码
if __name__ == "__main__":
    # 构建树:
    #     8
    #    / \
    #   6   10
    #  / \  / \
    # 5  7 9  11
    root = TreeNode(8)
    node6 = TreeNode(6, parent=root)
    node10 = TreeNode(10, parent=root)
    root.left = node6
    root.right = node10
    node5 = TreeNode(5, parent=node6)
    node7 = TreeNode(7, parent=node6)
    node6.left = node5
    node6.right = node7
    node9 = TreeNode(9, parent=node10)
    node11 = TreeNode(11, parent=node10)
    node10.left = node9
    node10.right = node11

    # 测试
    print(f"6的下一个节点: {get_next(node6).val}")
    print(f"7的下一个节点: {get_next(node7).val}")
    print(f"11的下一个节点: {get_next(node11)}")

# 输出:
# 6的下一个节点: 7
# 7的下一个节点: 8
# 11的下一个节点: None