首页 > 代码库 > [Leetcode] Recover Binary Search Tree
[Leetcode] 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?
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
OJ‘s Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.
Here‘s an example:
1 / 2 3 / 4 5The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}".
Solution:
这题的要点就是想到使用树的递归中序遍历，因为二叉查找树合法的情况，中序遍历的值是从小到大排列的。
当出现当前值比前一个值小的时候，就是存在不合法的节点。
----------------------------------------------------------------------------
解决方法是利用中序遍历找顺序不对的两个点，最后swap一下就好。
因为这中间的错误是两个点进行了交换，所以就是大的跑前面来了，小的跑后面去了。
所以在中序便利时，遇见的第一个顺序为抵减的两个node，大的那个肯定就是要被recovery的其中之一，要记录。
另外一个，要遍历完整棵树，记录最后一个逆序的node。
简单而言，第一个逆序点要记录，最后一个逆序点要记录，最后swap一下。
因为Inorder用了递归来解决，所以为了能存储这两个逆序点，这里用了全局变量，用其他引用型遍历解决也可以。
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { TreeNode pre; TreeNode first; TreeNode second; public void recoverTree(TreeNode root) { pre = null; first = null; second = null; inorderTraverse(root); int temp = first.val; first.val = second.val; second.val = temp; } private void inorderTraverse(TreeNode root) { // TODO Auto-generated method stub if(root==null) return; inorderTraverse(root.left); if(pre==null){ pre=root; //pre指针初始 }else{ if(pre.val>root.val){ if(first==null) first=pre; //第一个逆序点 second=root; //不断寻找最后一个逆序点 } pre=root; //pre指针每次后移一位 } inorderTraverse(root.right); }}
[Leetcode] Recover Binary Search Tree