首页 > 代码库 > [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?
https://oj.leetcode.com/problems/recover-binary-search-tree/
思路1：中序遍历生成序列，然后对其中错序的进行调整。 需要额外O(n)的空间。
思路2：中序遍历二叉树，记录当前指针cur的前一个节点pre，如果pre.val大于cur.val，表示有错序，多数情况错序有两次；如果有一次错序，说明就是相邻节点需要被交换。
public class Solution { private TreeNode pre; private TreeNode wrong1; private TreeNode wrong2; public void recoverTree(TreeNode root) { preOrder(root); int tmp = wrong1.val; wrong1.val = wrong2.val; wrong2.val = tmp; } private void preOrder(TreeNode root) { if (root == null) return; preOrder(root.left); if (pre != null && pre.val > root.val) { if (wrong1 == null) { wrong1 = pre; wrong2 = root; } else { wrong2 = root; } } pre = root; preOrder(root.right); } public static void main(String[] args) { TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15); root.left.right = new TreeNode(13); root.right.left = new TreeNode(7); new Solution().recoverTree(root); }}
参考：
http://blog.csdn.net/worldwindjp/article/details/21694179
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。