LeetCode 510. 二叉搜索树中的中序后继 II
题目描述
题意分析
给定一个带
parent指针的节点，返回中序遍历中紧接着访问的节点；若它已经是最后一个节点，返回空。中序顺序是左子树、当前节点、右子树，因此可以直接沿树结构定位后继，不需要从根重新遍历，也不必比较节点值。
解法：利用右子树与父指针
核心思路
[!blue]
若当前节点有右子树，中序遍历访问完它之后，下一步一定进入右子树。右子树最先访问的节点是一路向左得到的节点；它没有左孩子，所以不会还有其他节点排在它之前，直接返回它。
若没有右子树，当前节点及其整棵子树都已经访问完，需要沿父指针寻找尚未访问的祖先。上升过程中保持：以
cur为根的子树已经全部处理完，后继只能在它外面。当
cur是父节点的右孩子时，父节点早于这棵右子树被访问，现在父节点的整棵子树也完成了，因此继续把cur移到父节点。第一次遇到cur是左孩子时，父节点正好排在这棵已完成的左子树之后，它就是下一节点；直接返回cur.parent。若一直到根仍只能继续向上，说明已经访问完整棵树，没有后继。
解题步骤
- 有右子树，进入右孩子并持续向左。
- 否则沿父链上升，跳过当前节点属于右孩子的关系。
- 返回停止处的父节点，可以自然为空。
单节点树会因没有右子树和父节点而返回空；最右节点也会沿父链一直回到根。已有的空输入分支则直接返回空。
代码实现
class Solution {
public Node inorderSuccessor(Node node) {
if (node == null) {
return null;
}
// 有右子树时，后继就是其中最先被中序访问的节点
if (node.right != null) {
Node cur = node.right;
while (cur.left != null) {
cur = cur.left;
}
return cur;
}
Node cur = node;
// 从右孩子返回说明父节点已访问，继续向上寻找
while (cur.parent != null && cur.parent.right == cur) {
cur = cur.parent;
}
return cur.parent;
}
}
func inorderSuccessor(node *Node) *Node {
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(n)$。- 空间复杂度：$O(1)$，仅使用游标。
关键点总结
[!green]
- 有右子树时寻找右子树最左节点；没有右子树时寻找第一次从左孩子返回的祖先。
- 用父子指针判断从哪棵子树返回，不依赖节点值。
易错点总结
[!yellow]
- 有右子树却直接返回右孩子，会漏掉其更左后代。
- 无右子树就返回直接父亲，会返回已经访问过的节点。
- 上升结束返回当前节点而非父节点，后继位置少走一层。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 285. 二叉搜索树中的中序后继 | 中等 | 原题给出树根，可沿BST搜索后继；本题有parent指针，可从当前节点向上寻找祖先。 |
| 173. 二叉搜索树迭代器 | 中等 | 中序迭代器保存访问路径以连续取得后继，本题可直接利用节点已有的父指针。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！