首页 > 代码库 > [leetcode]Recover Binary Search Tree
[leetcode]Recover Binary Search Tree
Recover Binary Search Tree
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?
算法思路：
思路1：求出中序遍历序列，空间复杂度O(n)，tip要求只可以开O(1)空间。
代码略
思路2：中序遍历，遇到每个点，都记录其前驱，记录当前指针cur的前一个节点pre，如果pre.val大于cur.val，表示有错序，多数情况错序有两次；如果有一次错序，说明就是相邻节点需要被交换。
1 public class Solution { 2 TreeNode first = null,second = null,pre = null; 3 public void recoverTree(TreeNode root) { 4 findNode(root); 5 swap(first, second); 6 } 7 private void findNode(TreeNode root){ 8 if(root == null){ 9 return;10 }11 if(root.left != null ) findNode(root.left);12 if(pre != null && root.val < pre.val){13 if(first == null){14 first = pre;15 }16 second = root;17 }18 pre = root;19 if(root.right != null) findNode(root.right);20 }21 private void swap(TreeNode node1,TreeNode node2){22 int tem = node1.val;23 node1.val = node2.val;24 node2.val = tem;25 }26 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。