LeetCode-99.ツリーを復元(関連トピック:深度優先検索)

ツリー内の2つのノードが誤って交換されました.
構造を変えずに、この木を復元してください.
例1:

  : [1,3,null,null,2]

   1
  /
 3
  \
   2

  : [3,1,null,null,2]

   3
  /
 1
  \
   2

例2:

  : [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

  : [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

ステップ:

O(n)空間複雑度を用いた解法は容易に実現できる.

定数空間だけを使うソリューションを考え出せますか?

問題解決の考え方:
このツリーは、通常はインクリメンタルシーケンスであり、交換された2つのノードが見つかります(スタックの深さで優先的に検索されます).
Javaコード:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode pre = new TreeNode(Integer.MIN_VALUE), p = null, q = null;
        Stack stack = new Stack<>();

        while(null != root){
            stack.push(root);
            root = root.left;
        }
        while(!stack.isEmpty()){
            TreeNode treeNode = stack.pop();
            if(treeNode.val < pre.val){
                if(null == p){
                    p = pre;
                    q = treeNode;
                }
                else{
                    q = treeNode;
                }
            }
            pre = treeNode;

            if(null != treeNode.right){
                stack.push(treeNode.right);
                while(null != stack.peek().left)
                    stack.push(stack.peek().left);
            }
        }

        int tmp = p.val;
        p.val = q.val;
        q.val = tmp;
    }
}