Recover Binary Search Tree

Question

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

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

  1
 /
3
 \
  2

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

  3
 /
1
 \
  2

LeetCodeleetcode.com/problems/recover-binary-search-tree

Solution

/*解法一：直观思路
@param: TreeNode
@return: null
Algorithm: 1. inorder dfs
2.找到两个需要交换的数字
3.dfs recover
*/
List<Integer> list = new ArrayList<>();
public void recoverTree(TreeNode root) {
    if (root == null) return;
    dfs(root);
    list = new ArrayList<>(findSwapedNum(list));
    recover(root);
}

public void recover(TreeNode root) {
    if (root == null) return;
    if (root.val == list.get(0) || root.val == list.get(1)) {
        root.val = (root.val == list.get(0) ? list.get(1) : list.get(0));         
    }
    recover(root.left);
    recover(root.right);
}
    

public void dfs(TreeNode root) {
    if (root == null) return;
    dfs(root.left);
    list.add(root.val);
    dfs(root.right);
}

public List<Integer> findSwapedNum(List<Integer> list) {
    List<Integer> res = new ArrayList<>();
    int a = -1, b = -1;
    for (int i = 0; i < list.size()-1; i++) {
        if (list.get(i+1) < list.get(i)) {
            b = list.get(i+1);
            if (a == -1) a = list.get(i);
            else break;
        }            
    }
    res.add(a);
    res.add(b);        
    return res;
}

/*解法二 one pass TimeO(n) Space O(1)
@param: TreeNode
@return: null
Algorithm: one pass TimeO(n) Space O(1);
1. inOrder dfs把顺序找到，然后借助在array中找乱序两个元素思路，处理
2. 交换两个Node的val；
*/
TreeNode a, b;
TreeNode prev;
public void recoverTree(TreeNode root) {
    if (root == null) return;
    dfs(root);
    int temp = a.val;
    a.val = b.val;
    b.val = temp;
}

public void dfs(TreeNode root) {
    if (root == null) return;
    
    dfs(root.left);        
    if (prev != null && root.val < prev.val) {
        b = root;
        if (a == null) a = prev;
    }
    prev = root;
    dfs(root.right);
}