力扣第九十九题-恢复二叉搜索树 前言 一、思路 二、实现 三

发表于

「这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战」

前言

力扣第九十九题 恢复二叉搜索树 如下所示：

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶： 使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：

1
2
3
csharp复制代码输入： root = [1,3,null,null,2]
输出： [3,1,null,null,2]
解释： 3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

一、思路

题目中有一个重要的信息：树中有两个节点被错误的交换。那么我们只需要找到这两个节点，再将他两交换，就能获得一个正确的二叉搜索树。

那怎么样才能找到这两个错误交换的节点呢？

我们知道有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

我们发现 左子树的值是小于当前节点的值 且 右子树的值是大于当前节点的值。我们可以使用 中序遍历（左根右） 来遍历这个树，我们可以得到一个数组。我们再在这个数组中找到需要交换的两个节点，最后再将这两个节点的值交换即可。

举个例子

我们以下图的树 [3, 1, 4, null, null, 2]作为例子：

image.png

中序遍历后，得到的数组为 [1, 3, 2, 4]

数组中交换的位置为：第一次下降的位置和第一次上升的位置。（如果将递增数组看作一个斜向上的直线， 只有交换凸起处和下凹处的值，才能重新得到一条斜向上的直线）

很明显我们应该交换 2 和 3 的位置，交换后数组为 [1, 2, 3, 4]，树如下图所示：

image.png

为了避免第二次遍历数组，我们可以在遍历树的时候就生成一个数组。只需要判断当前值与前一个值的大小即可，如果当前值小于数组最后的一个值我们就记录这个节点。

二、实现

实现代码

实现代码与思路中保持一致，数组我们这里替换为 栈 来保存节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码    TreeNode x=null, y=null; // 下标

    public void recoverTree(TreeNode root) {
        dfs(root, new LinkedList<>());
        // 交换x,y的值（两种情况）
        int temp = x.val;
        x.val = y.val;
        y.val = temp;
    }

    public void dfs(TreeNode node, Deque<TreeNode> stack) {
        if (node == null) {
            return;
        }
        dfs(node.left, stack);
        if (!stack.isEmpty() && node.val < stack.peek().val) {
            if (x == null) {
                x = stack.peek();
            }
            y = node;
        }
        stack.push(node);
        dfs(node.right, stack);
    }

测试代码

1
2
3
4
java复制代码    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1, new TreeNode(3, null, new TreeNode(2)), null);
        new Number99().recoverTree(treeNode);
    }

结果

image.png

三、总结

感谢看到最后，非常荣幸能够帮助到你~♥

如果你觉得我写的还不错的话，不妨给我点个赞吧！如有疑问，也可评论区见~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%