forked from licong1112/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
RecoverBinarySearchTree.java
61 lines (51 loc) · 1.8 KB
/
RecoverBinarySearchTree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* Practiced on 12/19/2012
*
* 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?
*
* ==================================
* The idea is easy, but it is difficult to write the code which use O(1) space.
* 1. Maintain a TreeNode[] swapNodes, which stores the nodes that should be swapped.
* 2. Maintain TreeNode lastVisited, to keep track the last visited node.
*/
package com.congli.leetcode;
public class RecoverBinarySearchTree {
public static void main(String[] args)
{
RecoverBinarySearchTree test = new RecoverBinarySearchTree();
TreeNode root = new TreeNode(2);
TreeNode left = new TreeNode(3);
TreeNode right = new TreeNode(1);
root.left = left;
root.right = right;
test.recoverTree(root);
}
public void recoverTree(TreeNode root)
{
TreeNode[] swapNodes = new TreeNode[2];
helper(root, swapNodes, null);
if(swapNodes[0] != null)
{
int temp = swapNodes[0].val;
swapNodes[0].val = swapNodes[1].val;
swapNodes[1].val = temp;
}
}
private TreeNode helper(TreeNode root, TreeNode[] swapNodes, TreeNode lastVisited)
{
if(root == null) return lastVisited;
TreeNode leftLastVisited = helper(root.left, swapNodes, lastVisited);
if(leftLastVisited != null && root.val < leftLastVisited.val)
{
if(swapNodes[0] == null)
swapNodes[0] = leftLastVisited;
swapNodes[1] = root;
}
TreeNode rightLastVisited = helper(root.right, swapNodes, root);
return rightLastVisited == null ? root : rightLastVisited;
}
}