LeetCode 510. 二叉搜索树中的中序后继 II

Categories:

题目描述
思路分析
1. 解法一：利用右子树与父指针（推荐）
相似题目

题目描述

✅ 510. 二叉搜索树中的中序后继 II

思路分析

解法一：利用右子树与父指针（推荐）

核心思路：

若 p 有右子树，后继是右子树最左节点。

否则向上移动，直到当前节点是父节点的左孩子，此父节点即后继。

若一直向上到根都没有满足条件，则不存在后继。

复杂度分析：

时间复杂度：O(h)，其中 h 表示树高。

空间复杂度：O(1)。

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
}

相似题目

题目	难度	考察点
94. 二叉树的中序遍历	简单	中序遍历
173. 二叉搜索树迭代器	中等	BST
230. 二叉搜索树中第K小的元素	中等	BST
285. 二叉搜索树中的中序后继	中等	BST
700. 二叉搜索树中的搜索	简单	BST 查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/85626108