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

Categories:

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

题目描述

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

思路分析

解法一：利用父指针（推荐）

核心思路：

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

否则向上找到第一个“当前节点在其左子树中”的祖先。

若不存在该祖先，则无下一个节点。

复杂度分析：

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

空间复杂度：O(1)，仅使用常数额外空间。

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
}

相似题目

题目	难度	考察点
94. 二叉树的中序遍历	简单	中序遍历
98. 验证二叉搜索树	中等	BST
285. 二叉搜索树中的中序后继	中等	中序后继
116. 填充每个节点的下一个右侧节点指针	中等	指针
510. 二叉搜索树中的中序后继 II	中等	父指针

本文作者: HGNULB

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