作者:瑞景地产王琴 | 来源:互联网 | 2023-10-17 22:12
文章目录 题目:二叉搜索树中的两个节点被错误地交换。 基本思想1:中序遍历
题目:二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。
示例 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) 空间复杂度的解法很容易实现。 你能想出一个只使用常数空间的解决方案吗? 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/recover-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
基本思想1:中序遍历 二叉搜索树中序遍历的结果一定是升序序列,那么在该题中中序遍历的序列在交换两个元素后,成为升序序列。
首先,对二叉树进行中序遍历,并保存中序遍历的结果序列 寻找结果序列中第一个逆序的元素前面的元素pre 从元素pre一直往后寻找,当找到一个大于该元素的元素temp时,temp前面的元素post就是需要交换的元素 将pre和post这两个元素进行交换 空间复杂度为O(n)的写法 定义一个数组保存中序遍历的顺序
class Solution { public : vector< TreeNode* > vec; void recoverTree ( TreeNode* root) { inorder ( root) ; int pre &#61; 0 , i; for ( i &#61; 1 ; i < vec. size ( ) ; &#43;&#43; i) { if ( vec[ i] - > val > vec[ pre] - > val) &#43;&#43; pre; else break ; } for ( ; i < vec. size ( ) ; &#43;&#43; i) { if ( vec[ i] - > val > vec[ pre] - > val) break ; } -- i; int t &#61; vec[ i] - > val; vec[ i] - > val &#61; vec[ pre] - > val; vec[ pre] - > val &#61; t; } void inorder ( TreeNode* root) { if ( root &#61;&#61; NULL ) return ; inorder ( root- > left) ; vec. push_back ( root) ; inorder ( root- > right) ; } } ;
空间复杂度为O&#xff08;1&#xff09;的写法&#xff1a; 定义两个变量来保存逆序的两个节点
class Solution { public : void recoverTree ( TreeNode* root) { TreeNode* pre1 &#61; NULL , * pre2 &#61; NULL ; inorder ( root, pre1, pre2) ; int t &#61; pre1- > val; pre1- > val &#61; pre2- > val; pre2- > val &#61; t; } void inorder ( TreeNode* root, TreeNode* & pre1, TreeNode* & pre2) { if ( root &#61;&#61; NULL ) return ; inorder ( root- > left, pre1, pre2) ; if ( pre1 &#61;&#61; NULL ) { pre1 &#61; root; } else { if ( root- > val > pre1- > val && ( ! pre2 || root- > val < pre2- > val) ) { pre1 &#61; root; } else if ( pre2 &#61;&#61; NULL ) { pre2 &#61; pre1; pre1 &#61; root; } if ( ( root- > val < pre1- > val) && ( pre2) && ( pre2- > val > root- > val) ) { pre1 &#61; root; } } inorder ( root- > right, pre1, pre2) ; } } ;