问题描述:
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
原问题链接:https://leetcode.com/problems/recover-binary-search-tree/
问题分析
对于一棵二叉搜索树来说,如果它里面有两个节点的位置发生了交换,那么从它本身的性质来说,它这两个交换后的节点可能会出现每个节点在新的位置和它的左右子节点之间关系不符合原来的定义了。
这个时候,一个二叉搜索树的重要性质可以在这里起到大的作用。对于它来说,如果进行中序遍历的话,得到的结果是一个排序后递增的序列。可是如果我们交换了其中两个元素的话,里面就会有两个元素不符合递增的特性。
所以,我们可以通过中序遍历的时候将遍历过的所有元素加入到一个列表中。然后在结果列表里查找这两个元素就可以了。
那么,该怎么找这两个元素呢?因为交换了这两个元素之后,必然是一个大的元素放到了前面而一个小的元素放到了后面。所以我们从列表的第二个元素开始,每次比较当前元素和它的前一个元素。如果前一个元素比当前元素大,说明找到了这个大的元素。所以我们找到的第一个不符合条件的元素就是那个从后面被交换到前面的元素。而那个被前面交换到后面的元素则是最后一个不符合递增属性的元素。
找到这两个元素之后,我们交换设置这两个元素的值就可以了。详细的代码实现如下:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void recoverTree(TreeNode root) { List<TreeNode> list = new ArrayList<>(); traverse(root, list); int max = -1, min = -1; for(int i = 1; i < list.size(); i++) { if(list.get(i).val < list.get(i - 1).val) { max = i - 1; break; } } for(int i = max + 1; i < list.size(); i++) { if(list.get(i).val < list.get(i - 1).val) min = i; } if(max == -1 || min == -1) return; int temp = list.get(max).val; list.get(max).val = list.get(min).val; list.get(min).val = temp; } private void traverse(TreeNode node, List<TreeNode> list) { if(node == null) return; if(node.left != null) traverse(node.left, list); list.add(node); if(node.right != null) traverse(node.right, list); } }
相关推荐
leetcode的题目:Balanced Binary Tree
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 ...Recover Binary Search Tree 109. Convert Sorted List to Binary Search Tree 116. Populating Next Right Pointers in Each No
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
最终450 Love Babbar 450问题
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
Leetcode:Leetcode提交
leetcode LeetCode刷题 题号是LeetCode原题,题目是自己的解答 Easy 题号 题目 Tags Star Company HashMap :star: :star: :star: Integer :star: :star: String :star: String、Stack :star: :star: :star: ...
LeetCode 101:和你一起你轻松刷题(C++)
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
leetcode:leetcode刷题
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
Leetcode:LeetCode解题代码