LeetCode 补充题 12. 二叉树的下一个节点

约 5 分钟
文章信息 8 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 微软 猿辅导 高频面试题
标签
树
目录

题目描述

✅ 补充题 12. 二叉树的下一个节点

题意分析

给的不是整棵树的根，而是树里的某一个节点，这个节点除了左右孩子指针之外还带一个指向父节点的指针。要返回的是：把整棵树按「先左子树、再自己、后右子树」的顺序排成一列时，紧跟在这个节点后面的那个节点。

「只给节点、不给根」加上「节点带父指针」是本题最重要的信号。它意味着不必也不该去遍历整棵树——想拿到根还得先顺着父指针爬上去，然后中序走一遍找位置，那就白白浪费了父指针提供的局部信息。合理的做法是只在这个节点的邻域里做常数级的几步移动。

另外要注意题目并没有说这是二叉搜索树，节点值可以任意、可以重复，所以任何依赖「值有序」的比较都不成立，判断只能基于结构。边界有三处：传入的节点可能为空；节点可能位于中序序列的末尾，此时没有后继要返回空；节点也可能就是根。

解法：父指针定位中序后继

核心思路

中序遍历的顺序是「左子树 → 当前节点 → 右子树」。站在节点 node 上，它的后继只可能来自两个方向：

  • 有右子树：接下来会进入右子树，最先访问的是右子树的最左节点。
  • 没有右子树：当前子树已经访问完，需要沿父指针上行。只要当前节点是父节点的右孩子，父节点就已经访问过，仍要继续上行；第一次出现「当前节点是父节点的左孩子」时，该父节点尚未访问，就是后继。

上行时的不变量是：cur 所在子树已经完整访问。循环跳过所有已经访问过的祖先，退出时遇到的第一个未访问祖先就是答案；若一路走到根仍没找到，原节点就是中序序列末尾，返回空。

这个判断只依赖树结构，不依赖节点值，因此普通二叉树、重复值都适用。

解题步骤

  1. 节点为空，直接返回空。
  2. 若存在右孩子，从右孩子出发不断向左，返回最左节点。
  3. 否则令 cur = node，当 cur 是父节点的右孩子时持续上移。
  4. 返回 cur.parent：它可能是第一个未访问祖先，也可能为空。

例如中序序列为 d, b, e, a, f, c, g：b 有右子树，后继是 e；e 无右子树，先回到 b，此时 b 是 a 的左孩子，所以后继是 a；g 一路从右侧回到根，最终返回空。

代码实现

class Solution {
    public TreeLinkNode getNext(TreeLinkNode node) {
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            TreeLinkNode cur = node.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }

        TreeLinkNode cur = node;
        while (cur.parent != null && cur.parent.right == cur) {
            cur = cur.parent;
        }
        return cur.parent;
    }
}

func getNext(node *TreeLinkNode) *TreeLinkNode {
    if node == nil {
        return nil
    }
    if node.Right != nil {
        cur := node.Right
        for cur.Left != nil {
            cur = cur.Left
        }
        return cur
    }

    cur := node
    for cur.Parent != nil && cur.Parent.Right == cur {
        cur = cur.Parent
    }
    return cur.Parent
}

复杂度分析

  • 时间复杂度：$O(h)$，其中 $h$ 是树高；只会沿一条向下或向上的链移动。
  • 空间复杂度：$O(1)$，只使用游标指针。

关键点总结

  • 有右子树就找「右子树最左节点」，没有右子树就找「第一个从左侧进入的祖先」。
  • 父指针让后继查询无需回到根，也无需完整中序遍历。
  • 上行条件必须比较节点引用，不能用节点值；树不一定是二叉搜索树，值也可能重复。
  • 面试时要能说明：中序前驱是完全对称的逻辑——有左子树取最右节点，否则向上找第一次从右侧进入的祖先。

易错点总结

  • 有右子树却从当前节点向左走：找到的是前驱方向；必须先进入右子树。
  • 上行时跳过左孩子关系：方向写反会返回已经访问过的祖先；应跳过「当前是右孩子」的情况。
  • 循环结束返回 cur：真正的后继是 cur.parent。
  • 假设节点值有序：本题没有 BST 条件，按值比较没有正确性依据。
  • 未处理中序末尾节点：一路上行后父节点为空，应自然返回空。

相似题目

题目 难度 考察点
94. 二叉树的中序遍历 简单 中序序列的完整生成，可对照递归、显式栈与 Morris 三种写法
173. 二叉搜索树迭代器 中等 没有父指针，用栈把「下一个」摊还成 $O(1)$
285. 二叉搜索树中的中序后继 中等 只给根且保证是 BST，可用值比较自顶向下剪枝
510. 二叉搜索树中的中序后继 II 中等 与本题结构完全一致，只是限定了 BST 且节点不为空
LCR 053. 二叉搜索树中的中序后继 中等 同 285 的另一份题面，适合练自顶向下记录候选答案的写法
面试题 04.06. 后继者 中等 同样求 BST 后继，可对照递归写法与迭代写法的取舍
426. 将二叉搜索树转化为排序的双向链表 中等 把所有后继关系一次性物化成链表，适合高频查询场景