面试题-中序遍历的下一个节点

Categories:

题目描述
思路分析
1. 解法一：利用父指针向上回溯（推荐）
相似题目

题目描述

✅ 中序遍历的下一个节点

考察公司：洋钱罐

考察时间：2025.7.16

思路分析

解法一：利用父指针向上回溯（推荐）

核心思路：

若当前节点有右子树，则下一个节点是右子树的最左节点。

否则沿父指针向上寻找第一个“当前节点位于其左子树”的祖先。

若找不到这样的祖先，说明已经是中序最后一个节点。

复杂度分析：

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

空间复杂度：O(1)。

class Node {
    public Node parent;
    public Node left;
    public Node right;
    public int value;
}

class Solution {
    public Node GetNextNode(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;
        Node parent = node.parent;
        while (parent != null && parent.right == cur) {
            cur = parent;
            parent = parent.parent;
        }

        return parent;
    }
}

type Node struct {
	Parent *Node
	Left   *Node
	Right  *Node
	Val    int
}

func GetNextNode(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
	parent := node.Parent
	for parent != nil && parent.Right == cur {
		cur = parent
		parent = parent.Parent
	}

	return parent
}

相似题目

题目	难度	考察点
510. 二叉搜索树中的中序后继 II	中等	父指针
285. 二叉搜索树中的中序后继	中等	BST
94. 二叉树的中序遍历	简单	中序遍历
230. 二叉搜索树中第 K 小的元素	中等	BST
236. 二叉树的最近公共祖先	中等	树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/64256072