首页 > 算法 > [LeetCode每日一题]99. Recover Binary Search Tree
2020
02-19

[LeetCode每日一题]99. Recover Binary Search Tree

题目如下:

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

LeetCode-99 Recover Binary Search Tree
该题给定一棵二叉搜索树,树中正好有两个元素放反了,要求我们恢复这棵二叉搜索树。
首先让我们想一下BST的定义:
(1)左子树上所有的值小于根节点;
(2)柚子树上所有的值大于根节点;
(3)BST的任意一棵子树也是BST。
BST有这样一条性质:按照中序遍历BST可得到一个升序序列。由此中序遍历该题的BST得到的序列中必然有两个数放反了,我们要做的便是找到这两个数所在的节点并交换他们。
代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode biggerNode = null;  //放错的较大的节点
    TreeNode smallerNode = null; //放错的较小的节点
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE); //用于比较的前驱节点,root节点没有前驱节点,所以该节点的值初始化为MIN_VALUE

    public void recoverTree(TreeNode root) {
        dfs(root);
        //交换两节点的值
        int temp = biggerNode.val;
        biggerNode.val = smallerNode.val;
        smallerNode.val = temp;
        return;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (root.val < preNode.val) {
            if (biggerNode == null || biggerNode.val < preNode.val) {
                biggerNode = preNode;
            }
            if (smallerNode == null || root.val < smallerNode.val) {
                smallerNode = root;
            }
        }
        preNode = root;
        dfs(root.right);
        return;
    }
}

该算法每个节点访问一次,时间复杂度为O(n),开了三个全局变量,空间复杂度为O(1)。

最后编辑:
作者:lwg0452
这个作者貌似有点懒,什么都没有留下。
捐 赠如果您觉得这篇文章有用处,请支持作者!鼓励作者写出更好更多的文章!

留下一个回复

你的email不会被公开。