如何输入节点P，输出其在二叉树先序、中序、后序遍历中的后续节点

你已经实现了三种遍历返回全节点序列的方法，直接基于现有代码扩展即可，实现逻辑非常简单：

1. 调用对应遍历方法拿到整棵树的遍历序列
2. 定位目标节点在序列中的索引
3. 返回索引位之后的所有元素

基础实现（直接复用现有代码，适合中小规模树） #

给你的二叉树类添加如下通用方法即可：

def get_following_nodes(self, target_val, traverse_type: str):
    """
    :param target_val: 目标节点的data值
    :param traverse_type: 遍历类型，可选值 'pre'(先序)/'in'(中序)/'post'(后序)
    :return: 遍历规则下位于目标节点之后的所有节点值列表
    """
    # 获取对应遍历的全量序列
    if traverse_type == "pre":
        traverse_list = self.pre_order_traversal()
    elif traverse_type == "in":
        traverse_list = self.in_order_traversal()
    elif traverse_type == "post":
        traverse_list = self.post_order_traversal()
    else:
        raise ValueError("traverse_type only support 'pre'/'in'/'post'")
    
    # 定位目标节点
    try:
        target_idx = traverse_list.index(target_val)
    except ValueError:
        # 目标节点不存在时返回空列表
        return []
    
    # 返回目标节点之后的所有元素
    return traverse_list[target_idx + 1:]

调用示例 #

对应你给出的示例，先序遍历结果为(1,2,3,4,5,6)，输入目标节点4：

# root为二叉树根节点
res = root.get_following_nodes(4, "pre")
# 返回结果为 [5,6]，符合预期

注意：如果你的二叉树存在多个相同data的节点，建议修改现有遍历方法返回节点对象而非节点值，匹配节点对象位置即可避免找错目标。

优化实现（无需全量遍历，适合大规模树） #

如果你的树节点量级很大，全量遍历会浪费性能，可以修改遍历逻辑，找到目标节点后再开始记录后续节点，无需遍历完整棵树，这里给出先序遍历的优化示例，中序、后序调整节点处理顺序即可：

def get_pre_following_optimized(self, target_val, found=False, res=None):
    if res is None:
        res = []
    # 已找到目标节点，直接记录当前节点
    if found:
        res.append(self.data)
    # 未找到目标节点，判断当前节点是否为目标
    else:
        if self.data == target_val:
            found = True
    # 递归左子树
    if self.left:
        found, res = self.left.get_pre_following_optimized(target_val, found, res)
    # 递归右子树
    if self.right:
        found, res = self.right.get_pre_following_optimized(target_val, found, res)
    return found, res

# 调用方式
_, result = root.get_pre_following_optimized(4)
# result即为目标节点之后的元素列表

内容的提问来源于stack exchange，提问作者KMP