前言

算法题刷多了，知识点也有了一定的积累，这个时候就需要见招拆招了，知识点灵活组合。但是想拆招，就得知道题目给的是什么招，如果不能从题目中挖掘出来是什么招，何谈拆招？
解题一般流程：根据题意模拟理解->发现问题->分析问题(分类整理)->见招拆招。

一、恢复二叉搜索树

二、见招拆招

package everyday.medium;

import java.util.ArrayList;
import java.util.List;

// 恢复二叉搜索树
public class RecoverTree {
    /*
    target：有两个节点不满足大小关系，将其交换。
    我之前没有分析题目，只进行的简单的遍历，找到一处前后不等的情况，就将其交换，正如上面写的target。
    总结：没有静下心来分析题目，充分理解题目，从而打开正确的分析之路，不注意细节，方向就打不开。

    分析如下，
    交换两个元素，会导致中序递增序列有两处递减，设第一处a > b;第二处 c > d;把最小d和最大的a交换，则序列变得递增。
    当然，如果是两个相邻的，则只有一处不等，设a > b,把最小的b和最大的a交换，则序列变得递增。

    记录递减的4/2个节点，根据情况进行交换。
     */

    public void recoverTree(TreeNode root) {
        // 中序遍历，寻找递减的4/2个节点，放入list之中。
        inOrder(root);
        // 根据情况处理交换。
        // 设需要交换的为x和y
        TreeNode x = error.get(0), y = error.size() == 2 ? error.get(1) : error.get(3);
        // 交换x 和 y的值即可，不用修改结构。
        // swap
        int t = x.val;
        x.val = y.val;
        y.val = t;
    }

    List<TreeNode> error = new ArrayList<>();
    TreeNode pre = null;

    private void inOrder(TreeNode root) {
        // 到达空节点，结束递归。
        if (root == null) return;
        // 遍历左子树
        inOrder(root.left);
        // 中序遍历。
        if (pre != null && pre.val > root.val) {
            error.add(pre);
            error.add(root);
        }
        // 更新前驱。
        pre = root;
        // 遍历右子树。
        inOrder(root.right);
    }

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = 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

总结

1）恢复二叉树，为什么会出现错误的二叉树？提出关键问题。
2）解题一般流程：根据题意模拟理解->发现问题->分析问题(分类整理)->见招拆招。

参考文献

[1] LeetCode 恢复二叉搜索树