1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Recover Binary Search Tree
5+ Difficulty: High
6+ Source: https://oj.leetcode.com/problems/recover-binary-search-tree/
7+ Notes:
8+ Two elements of a binary search tree (BST) are swapped by mistake.
9+ Recover the tree without changing its structure.
10+ Note:
11+ A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
12+
13+ Solution: 1. recursive solution. O(n) space. get inorder list first.
14+ 2. recursive solution. O(n) space. with only auxiliary two pointers.
15+ 3. Use a stack. Iteration.
16+ 4. TBD. Morris inorder traversal. O(1) space. with only auxiliary two pointers.
17+ */
18+
19+ /**
20+ * Definition for binary tree
21+ * public class TreeNode {
22+ * int val;
23+ * TreeNode left;
24+ * TreeNode right;
25+ * TreeNode(int x) { val = x; }
26+ * }
27+ */
28+ public class Solution {
29+ public void recoverTree_1 (TreeNode root ) {
30+ if (root ==null )return ;
31+ ArrayList <TreeNode >res =new ArrayList <TreeNode >();
32+ inorderTraversal (root ,res );
33+ TreeNode first =null ,second =null ;
34+ for (int i =1 ;i <res .size (); ++i ) {
35+ if (res .get (i ).val >res .get (i -1 ).val )
36+ continue ;
37+ if (first ==null )first =res .get (i -1 );
38+ second =res .get (i );
39+ }
40+ if (first ==null )return ;
41+ int tmp =first .val ;
42+ first .val =second .val ;
43+ second .val =tmp ;
44+ }
45+ public void inorderTraversal (TreeNode root ,ArrayList <TreeNode >res ) {
46+ if (root ==null )return ;
47+ inorderTraversal (root .left ,res );
48+ res .add (root );
49+ inorderTraversal (root .right ,res );
50+ }
51+ public void recoverTree_2 (TreeNode root ) {
52+ if (root ==null )return ;
53+ TreeNode []res =new TreeNode [3 ];// 0->pre, 1->first, 2->second
54+ recoverRe2 (root ,res );
55+ int tmp =res [1 ].val ;
56+ res [1 ].val =res [2 ].val ;
57+ res [2 ].val =tmp ;
58+ }
59+ public void recoverRe2 (TreeNode root ,TreeNode []res ) {
60+ if (root ==null )return ;
61+ recoverRe2 (root .left ,res );
62+ if (res [0 ] !=null &&res [0 ].val >root .val ) {
63+ if (res [1 ] ==null )res [1 ] =res [0 ];
64+ res [2 ] =root ;
65+ }
66+ res [0 ] =root ;
67+ recoverRe2 (root .right ,res );
68+ }
69+
70+ public void recoverTree_3 (TreeNode root ) {
71+ if (root ==null )return ;
72+ Stack <TreeNode >stk =new Stack <TreeNode >();
73+ TreeNode cur =root ,pre =null ,first =null ,second =null ;
74+ while (stk .isEmpty () ==false ||cur !=null ) {
75+ if (cur !=null ) {
76+ stk .push (cur );
77+ cur =cur .left ;
78+ }else {
79+ cur =stk .pop ();
80+ if (pre !=null &&pre .val >cur .val ) {
81+ if (first ==null )first =pre ;
82+ second =cur ;
83+ }
84+ pre =cur ;
85+ cur =cur .right ;
86+ }
87+ }
88+ if (first ==null )return ;
89+ int tmp =first .val ;
90+ first .val =second .val ;
91+ second .val =tmp ;
92+ }
93+ }
