Leetcode99. 恢复二叉搜索树

题目传送：https://leetcode.cn/problems/recover-binary-search-tree/

运行效果

代码如下

class Solution {
    //用于存储中序遍历的结果
  List<Integer> list = new ArrayList();

  public void recoverTree(TreeNode root) {
    // 1、先对这颗二叉树进行中序遍历，然后依次存放进list中
    inOrder(root);
    // m和n用于记录需要交换的2个位置
    int m = -1;
    int n = -1;

    for (int i = 0; i < list.size() - 1; i++) {
      // 第一种情况  非相邻交换： 1 2 3 4 5 6 7   交换 2和6的位置    变成1 6 3 4 5 2 7
      // 第二种情况  相邻交换： 1 2 3 4 5 6 7 交换2和3的2位置  变成  1 3 2 4 5 6 7
      if (list.get(i) > list.get(i + 1)) {
        if (m == -1) {
          m = i;
          continue;
        }
        if (n == -1) {
          n = i + 1;
        }
      }
    }
    // 如果m和n  都不等于-1，说明是属于第一种情况
    if (m != -1 && n != -1) {
      // 交换m和n位置的元素即可
      Integer val1 = list.get(m);
      Integer val2 = list.get(n);
      swapNode(val1,val2,root);
    }
    // 如果m != -1   ，但是n== -1   说明是属于第二种情况
    if (m != -1 && n == -1) {
      // 交换m和m+1位置的元素即可
      Integer val1 = list.get(m);
      Integer val2 = list.get(m+1);
      swapNode(val1,val2,root);
    }
  }
  /*
   * @description: 在二叉树中交换 i和j位置的元素
   * @date: 2022/8/27 16:38
   * @param: a
   * @return: a
   */
  public void swapNode(int val1, int val2, TreeNode root) {
    if (root == null) {
      return;
    }
    // 1、先遍历左子树
    swapNode(val1,val2,root.left);
    // 2、遍历当前根节点
    if (root.val == val1) {
      root.val = val2;
    } else if (root.val == val2) {
      root.val = val1;
    }
    // 3、最后遍历右子树
    swapNode(val1,val2,root.right);
  }

  /*
   * @description: 中序遍历二叉树
   * @date: 2022/8/27 16:19
   * @param: a
   * @return: a
   */
  public void inOrder(TreeNode root) {
    if (root == null) {
      return;
    }
    // 1、先遍历左子树
    inOrder(root.left);
    // 2、遍历当前根节点
    list.add(root.val);
    // 3、最后遍历右子树
    inOrder(root.right);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79