Leetcode[99] Recover Binary Search Tree
07 Nov 2015###Task1 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?
###Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
res = []
self.inorder(res, root)
first = None
second = None
for i in range(1, len(res)):
if res[i].val < res[i - 1].val:
if first == None:
first = res[i - 1]
second = res[i]
else:
second = res[i]
break
first.val, second.val = second.val, first.val
def inorder(self, res, root):
if root == None:
return
self.inorder(res, root.left)
res.append(root)
self.inorder(res, root.right)
####O(1) space
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
wrong = [None, None]
self.last = None
self.inorder(root, wrong)
wrong[0].val, wrong[1].val = wrong[1].val, wrong[0].val
def inorder(self, root, wrong):
if root == None:
return
self.inorder(root.left, wrong)
if self.last:
if self.last.val > root.val:
if wrong[0] == None:
wrong[0] = self.last
wrong[1] = root
else:
wrong[1] = root
return
self.last = root
self.inorder(root.right, wrong)
###Java ####O(n) space
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
public void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
list.add(root);
inorder(root.right);
return;
}
public void swap(TreeNode first, TreeNode second) {
int temp = first.val;
first.val = second.val;
second.val = temp;
}
public void recoverTree(TreeNode root) {
if (root == null) {
return ;
}
inorder(root);
TreeNode first = null;
TreeNode second = null;
TreeNode prev = list.get(0);
for (int i = 1; i < list.size(); i++) {
TreeNode cur = list.get(i);
if (prev.val > cur.val) {
if (first == null) {
first = prev;
second = cur;
} else {
second = cur;
break;
}
}
prev = cur;
}
swap(first, second);
}
}
####O(1) space
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode first = null;
TreeNode second = null;
TreeNode prev = new TreeNode(Integer.MIN_VALUE);
public void recoverHelper(TreeNode root) {
if (root == null) {
return;
}
recoverHelper(root.left);
if (first == null && prev.val > root.val) {
first = prev;
//second = root;
}
if (first != null && prev.val > root.val) {
second = root;
}
prev = root;
recoverHelper(root.right);
return;
}
public void swap(TreeNode first, TreeNode second) {
int temp = first.val;
first.val = second.val;
second.val = temp;
}
public void recoverTree(TreeNode root) {
if (root == null) {
return ;
}
recoverHelper(root);
swap(first, second);
}
}
###Points
- Extended inorder traversal
- To record first&second in recursion, either declare them globally or pass thru a container(list…)
- Pay attention to the special case: when the swapped nodes are adjacent! So the first time detect anormaly, save both nodes.