二叉树递归前序遍历中如何查找节点的后继元素

首先明确前序遍历的顺序是：根节点 → 左子树 → 右子树，对应你给出的示例树，前序序列为：1 → 2 → 4 → 5 → 7 → 3 → 6。所以各节点的标准后继应该是：

• 节点2的后继是4
• 节点4的后继是5
• 节点5的后继是7
• 节点7的后继是3
• 节点3的后继是6

你当前代码的核心问题是回溯父节点时的逻辑错误：当递归调用preordernextRecursive(node.parent)时，会重新判断父节点的左/右孩子，导致返回错误结果（比如节点7回溯到5时，原代码会返回5的右孩子7，而非正确的3）。

修正后的递归代码 #

public E preorderNextRecursive(Node<E> node) {
    if (node == null) {
        return null;
    }
    
    // 规则1：当前节点有左孩子，左孩子就是前序遍历的下一个节点
    if (node.left != null) {
        return node.left.element;
    }
    
    // 规则2：无左孩子但有右孩子，右孩子就是下一个节点
    if (node.right != null) {
        return node.right.element;
    }
    
    Node<E> parent = node.parent;
    // 已经回溯到根节点，且根节点无未访问的右子树，返回null
    if (parent == null) {
        return null;
    }
    
    // 规则3：当前节点是父节点的左孩子，且父节点有右子树，右子树的根就是下一个节点
    if (parent.left == node && parent.right != null) {
        return parent.right.element;
    }
    
    // 规则4：当前节点是父节点的右孩子，说明父节点的左右子树都已遍历完，递归回溯父节点的后继
    return preorderNextRecursive(parent);
}

代码逻辑解释 #

1. 基础判断：如果传入节点为null，直接返回null。
2. 左孩子优先：前序遍历先访问左子树，所以存在左孩子时直接返回左孩子元素。
3. 右孩子次之：无左孩子时，右孩子是下一个访问的节点。
4. 回溯父节点：
   • 如果当前节点是父节点的左孩子，且父节点有右子树，那么右子树的根就是下一个节点。
   • 如果当前节点是父节点的右孩子，说明父节点的所有子节点都已遍历，需要继续递归回溯父节点，直到找到符合条件的父节点或回溯到根。

测试示例 #

• 传入节点7：无左右孩子，回溯到父节点5；节点7是5的右孩子，继续递归回溯到父节点2；节点5是2的右孩子，继续递归回溯到父节点1；节点2是1的左孩子，且1有右子树3，返回3的元素，符合预期。
• 传入节点5：有右孩子7，返回7的元素，符合预期。
• 如果你确实需要节点2的后继是5，那说明你要找的不是标准前序后继，而是左子树遍历完成后的下一个节点，这本质是找节点4的后继，可基于当前逻辑调整目标节点。

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