Recover BST...直接对调一下节点的值真的可以吗

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?

感觉一般情况下，能不直接给二叉树/链表改值的，都不会直接改值
这道题要求用O(1)空间复杂度，然后我只能想到找到两个对调节点以后改值了。看了一下我一直参考的“正确答案”也是这么写的= =
这算不算是偷懒啊。。。面试官会问如果不改值怎么做吗

我代码这么写的：

1. public class Solution {
   
2.    
   
3.     private TreeNode current = null;
   
4.     private TreeNode mistaken1 = null;
   
5.     private TreeNode mistaken2;
   
6.    
   
7.     public void recoverTree(TreeNode root) {
   
8.         traverse(root);
   
9.         int temp = mistaken1.val;
   
10.         mistaken1.val = mistaken2.val;
    
11.         mistaken2.val = temp;
    
12.     }
    
13.    
    
14.     public void traverse(TreeNode root) {
    
15.         if (root != null) {
    
16.             traverse(root.left);
    
17.             if (current != null && root.val < current.val) {
    
18.                 if (mistaken1 == null) {
    
19.                     mistaken1 = current;
    
20.                 }
    
21.                 if (mistaken1 != null) {
    
22.                     mistaken2 = root;
    
23.                 }
    
24.             }
    
25.             current = root;
    
26.             traverse(root.right);
    
27.         }
    
28.     }
    
29. }

复制代码

我觉得除了直接改值没别的办法了吧。。如果这不允许，还原二叉树就只能修改结构了。

另外，我看网上很多答案都用了递归。递归调用是会用到递归栈的，空间复杂度是O(n), 我觉得不合题目要求。

http://www.geeksforgeeks.org/ino ... -and-without-stack/