LeetCode 99. 恢复二叉搜索树

Categories:

题目描述
思路分析
1. 解法一：中序遍历定位异常节点（推荐）
相似题目

题目描述

✅ 99. 恢复二叉搜索树

思路分析

解法一：中序遍历定位异常节点（推荐）

核心思路：

BST 中序遍历应当是递增序列。

若有两个节点交换，会出现两处逆序。

记录第一个逆序的前一个节点与最后一个逆序的当前节点，最后交换二者值。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(h)，其中 h 表示树高（递归/栈深）。

class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode first = null;
        TreeNode second = null;
        TreeNode prev = null;

        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        // 中序遍历定位逆序节点
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (prev != null && prev.val > cur.val) {
                if (first == null) {
                    first = prev;
                }
                second = cur;
            }
            prev = cur;
            cur = cur.right;
        }

        if (first != null && second != null) {
            int tmp = first.val;
            first.val = second.val;
            second.val = tmp;
        }
    }
}

func recoverTree(root *TreeNode) {
	var first, second, prev *TreeNode
	stack := make([]*TreeNode, 0)
	cur := root

	// 中序遍历定位逆序节点
	for cur != nil || len(stack) > 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}

		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if prev != nil && prev.Val > cur.Val {
			if first == nil {
				first = prev
			}
			second = cur
		}
		prev = cur
		cur = cur.Right
	}

	if first != nil && second != nil {
		first.Val, second.Val = second.Val, first.Val
	}
}

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	BST
230. 二叉搜索树中第 K 小的元素	中等	中序遍历
285. 二叉搜索树中的中序后继	中等	BST
701. 二叉搜索树中的插入操作	中等	BST
450. 删除二叉搜索树中的节点	中等	BST

本文作者: HGNULB

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