leetcode99-恢复二叉搜索树

原题

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下,恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

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

解法

思想

这道题可以使用中序遍历得到一个序列,这个序列的特征是一个有序序列中的两个元素被交换了,那么问题就变成如何找到这两个元素。

看一个例子: 1 2 8 6 7 4 9 ,有序序列中的两个元素被交换了一定会造成一个较大的元素交换到了前面(8),一个较小的元素交换到了后面(4),体现在序列中就是两个异常的情况:6比8小,4比7小。所以可以判断:第一次出现的某节点比前驱节点的值要小的情况,前驱节点就是一个被交换了的节点,而第二次出现的某节点比前驱节点的值要小的情况,该节点就是第二个被交换了的节点。

而还有一种可能是,两个连续的元素被交换了,如:1 3 2 4,出现的情况就是只出现一次某节点比前驱节点的值要小的情况,那么两个被交换的节点就分别是当前节点(2)和其前驱节点(3)。

找到了这两个节点,就可以使用值交换将二叉搜索树恢复回来。

代码

递归中序遍历:

class Solution {
    TreeNode pred;
    TreeNode former,latter;
    public void recoverTree(TreeNode root) {
        recurTree(root);
        int cache = former.val;
        former.val = latter.val;
        latter.val = cache;
    }
    public void recurTree(TreeNode root){
        if(root == null) return;
        recurTree(root.left);
        if(pred == null) pred = root;
        else if(root.val < pred.val) {
            if(former == null) former = pred;
            latter = root;
        }
        pred = root;
        recurTree(root.right);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode99-%e6%81%a2%e5%a4%8d%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月29日
下一篇 2020年3月1日

相关推荐

  • leetcode343-整数拆分

    原题 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1…

    算法 2020年4月13日
    0110
  • 'leetcode50-Pow(x,n)'

    原题 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例1: 输入: 2.00000, 10 输出: 1024.00000 示例2: 输入: 2.10000, 3 输…

    算法 2020年1月5日
    0170
  • leetcode125-验证回文串

    原题 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明: 本题中,我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a …

    算法 2020年5月21日
    0140
  • leetcode557-反转字符串中的单词III

    原题 给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例1: 输入: “Let’s take LeetCode contest” 输出: …

    算法 2019年11月23日
    0120
  • leetcode138-复制带随机指针的链表

    这道题和leetcode133-克隆图有异曲同工之妙。 原题 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。…

    2019年12月17日
    0330
  • leetcode150-逆波兰表达式求值

    原题 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只保留整数部分。 给定逆波兰…

    2019年12月12日
    0110
  • leetcode46-全排列

    原题 给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [   [1,2,3],   [1,3,…

    算法 2020年3月3日
    0180
  • leetcode121-买卖股票的最佳时机

    原题 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在…

    算法 2020年3月9日
    0100
  • leetcode1014-最佳观光组合

    原题 给定正整数数组 A,A[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的距离为 j - i。 一对景点(i < j)组成的观光组合的得分为(A[i]…

    算法 2020年6月17日
    01950
  • leetcode836-矩形重叠

    原题 矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。 如果相交的面积为正,则称两矩形重叠。需要…

    算法 2020年3月18日
    0450

发表回复

登录后才能评论