LeetCode 补充题 12. 二叉树的下一个节点
题目描述
给定普通二叉树中的一个节点
node，请返回它在中序遍历中的下一个节点。如果不存在下一个节点，返回空。每个节点除
left、right指针外，还包含指向父节点的parent指针。二叉树不一定是二叉搜索树，因此不能按照节点值的大小寻找后继。
示例 1：
输入：树的层序表示为 [2,1,3]，node 指向值为 1 的节点
输出：值为 2 的节点
解释：中序遍历顺序为 [1,2,3]。
示例 2：
输入：树的层序表示为 [2,1,3]，node 指向值为 3 的节点
输出：null
提示：
- 输入是节点引用；示例中的节点值仅用于说明节点身份。
- 中序遍历的顺序为左子树、当前节点、右子树。
-
node为空时返回空。
题意分析
给定普通二叉树中的一个节点，每个节点除了左右孩子指针，还能通过父指针
parent向上移动。要求返回该节点在中序遍历中的下一个节点；不存在后继时返回空，输入节点为空时也返回空。中序遍历的顺序是左子树、当前节点、右子树。题目只给出了树的结构，并不保证是二叉搜索树，因此“下一个”指遍历顺序紧随其后的节点，不能根据节点值大小来判断，也不是简单返回右孩子或父节点。
解法：父指针定位中序后继
核心思路
[!blue]
刚访问完当前节点时，它的左子树已经全部访问过，接下来优先处理右子树。如果右子树存在，中序遍历首先到达的是右子树中一路向左走到的节点；这个节点没有更早要访问的左子树，所以它就是后继。注意应先进入右子树，再寻找最左节点。
如果没有右子树，当前节点这一部分已经完成，只能沿父指针回到祖先。关键是判断回到父节点时，刚完成的是父节点的哪一侧子树。
若当前节点是父节点的右孩子，说明父节点自身早已在进入右子树之前访问过；现在右子树也完成了，父节点这整部分都已结束，应继续向上跳过它。这个判断沿上行链反复进行。
第一次发现当前节点是父节点的左孩子时，说明刚完成父节点的左子树，而父节点自身还未访问，因此父节点就是下一个节点，可以立即返回。如果一直从右侧回溯到根，再也没有父节点，则原节点已是整棵树中序遍历的最后一项，后继为空。
整个定位过程只依赖父子指针关系。判断左、右孩子时比较的是节点对象是否相同，即使节点值重复，也不影响结构上的后继。
解题步骤
- 输入节点为空时返回空。
- 若存在右孩子，先进入右子树，然后沿左孩子指针一直向下，返回最终到达的最左节点。
- 否则用
cur从原节点开始，沿父指针回溯。- 只要父节点存在且
cur是它的右孩子，就令cur = cur.parent，跳过已经访问完的祖先。- 循环结束时返回
cur.parent：它要么是首次从左侧回到的父节点，要么为空。
代码实现
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)。只移动节点指针，不需要遍历整棵树、记录序列或使用递归栈。
关键点总结
[!green]
- 两种情况直接来自中序顺序：右子树尚未访问时先进入右侧，否则返回祖先。
- 从右孩子回来的父节点已经访问过，从左孩子回来的父节点才是下一候选。
- 普通二叉树也能使用该方法，因为定位依据是结构而非数值顺序。
- 父指针已经提供返回路径，不需要额外的栈保存祖先。
易错点总结
[!yellow]
- 有右子树时直接返回右孩子：右孩子还可能有左子树，应继续寻找右子树的最左节点。
- 从原节点开始一路向左：会进入已经访问过的区域，必须先进入右子树。
- 无右子树就直接返回父节点：原节点位于父节点右侧时，父节点已经访问过，需要继续上行。
- 上行时跳过左孩子关系：第一次从左侧回到父节点就已经找到后继，继续跳过会漏掉正确答案。
- 结束后返回
cur：它属于已经访问完的部分，应返回尚未访问的cur.parent。- 用值相等判断父子关系：节点值可能重复，关系判断必须使用节点引用。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 510. 二叉搜索树中的中序后继 II | 中等 | 父指针寻找中序后继的结构过程不依赖节点值大小，因此普通二叉树也可复用。 |
| 285. 二叉搜索树中的中序后继 | 中等 | 原题给BST根，可按值寻找严格更大候选，本题普通树不能使用这个有序剪枝。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！