@@ -13,7 +13,7 @@ A solution using O(n) space is pretty straight forward. Could you devise a const
1313 Solution: 1. recursive solution. O(n) space. get inorder list first.
1414 2. recursive solution. O(n) space. with only auxiliary two pointers.
1515 3. Use a stack. Iteration.
16- 4.TBD. Morris inorder traversal. O(1) space. with only auxiliary two pointers.
16+ 4. Morris inorder traversal. O(1) space. with only auxiliary two pointers.
1717*/
1818
1919/**
@@ -90,4 +90,39 @@ public void recoverTree_3(TreeNode root) {
9090first .val =second .val ;
9191second .val =tmp ;
9292 }
93+
94+ public void recoverTree_4 (TreeNode root ) {
95+ if (root ==null )return ;
96+ TreeNode cur =root ,pre =null ,first =null ,second =null ;
97+ while (cur !=null ) {
98+ if (cur .left ==null ) {
99+ if (pre !=null &&pre .val >cur .val ) {
100+ if (first ==null )first =pre ;
101+ second =cur ;
102+ }
103+ pre =cur ;
104+ cur =cur .right ;
105+ }else {
106+ TreeNode node =cur .left ;
107+ while (node .right !=null &&node .right !=cur )
108+ node =node .right ;
109+ if (node .right !=null ) {
110+ if (pre !=null &&pre .val >cur .val ) {
111+ if (first ==null )first =pre ;
112+ second =cur ;
113+ }
114+ pre =cur ;
115+ node .right =null ;
116+ cur =cur .right ;
117+ }else {
118+ node .right =cur ;
119+ cur =cur .left ;
120+ }
121+ }
122+ }
123+ if (first ==null )return ;
124+ int tmp =first .val ;
125+ first .val =second .val ;
126+ second .val =tmp ;
127+ }
93128}
