【解题思路】二叉搜索树类问题

二叉搜索树定义：

左子树都小于根节点值，右子树都大于根节点值，同时各节点的左右子树都是二叉搜索树。

二叉搜索树中序遍历结果为严格递增序列，利用这个特点解决二叉搜索树类问题

---

题目一： 验证二叉搜索树

---

题目描述： 给定一颗二叉树，判断其是否是一颗二叉搜索树
示例：

思路：
中序遍历二叉搜索树， 将节点值加入 List 中。 判断List是否满足严格递增，若满足则是二叉搜索树。
代码：

    // 存储节点中序遍历序列
    List<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        dfs(root);
        // 只含一个节点，则一定是二叉搜索树
        if(list.size() == 1){
            return true;
        }
        // 判断是否严格递增
        for(int i=1; i<list.size(); i++){
            if(list.get(i) <= list.get(i-1)){
                return false;
            }
        }
        return true;
    }

    // 获取中序遍历序列
    public void dfs(TreeNode node){
        if(node == null){
            return;
        }
        dfs(node.left);
        list.add(node.val);
        dfs(node.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

优化思路：
上述代码通过先得到序列，再进行判断的方式得到结果。而对本题来说，我们所遍历到的节点的值只需与其中序遍历的前一个节点值进行比较，判断其是否满足递增。因此，可以定义一个临时变量pre存储当前递归节点的中序遍历前一个节点的值, 通过判断当前节点值是否大于pre值， 来判断是否是二叉搜索树。

优化后代码：

   // 临时变量，用于存储当前递归节点的前一个节点值，主要初始值为Long的最小值，因为二叉搜索树val可能为整数最小值
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {

        if(root == null){
            return true;
        }
        // 左子树不满足二叉搜索树，则肯定不是二叉搜索树； 左子树是二叉搜索树，则还需判断右子树是否是二叉搜索树
        if(!isValidBST(root.left)){
            return false;
        }

        // 中序遍历的当前节点的前一个节点值 大于 当前节点的值， 则直接返回false， 肯定不是二叉搜索树
        if(pre >= root.val){
            return false;
        }
        // 更新前一节点值
        pre = root.val;

        // 左子树满足二叉搜索树， 返回右子树是否满足二叉搜索树
        return isValidBST(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

---

题目二： 恢复二叉搜索树

---

题目描述：
二叉搜索树交换两节点使得其结果不满足二叉搜索树条件，请原地修改该不满足条件的二叉搜索树，使得该二叉树变为二叉搜索树
示例：

本题也是一道可利用二叉搜索树中序遍历结果为严格递增序列这一性质解决的问题
思路： 我们可以观察题中给定的交换两个节点的二叉搜索树有何特点，以上图示例为例子，上图示例中序遍历结果为：3 -> 2 -> 1
分析可得中序遍历过程中一定存在两处使得 pre.val > node.val ，因此只要找出 pre.val > node.val 的两处位置， 记录下出现问题的节点， 第一次记录 pre , 第二次记录 node, 再交换 这两个被记录节点的值即可。
代码：

   TreeNode first = null; // 记录第一个出现问题节点的位置
    TreeNode second = null; // 记录第二个出现问题节点的位置
    TreeNode pre = new TreeNode(Integer.MIN_VALUE); // 记录中序遍历过程中出现的前一个节点

    public void recoverTree(TreeNode root) {
        dfs(root);
        // 交换两个出现问题节点的值
        if(first != null && second != null){
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }

    public void dfs(TreeNode root){

        if(root == null){
            return;
        }
        dfs(root.left);
        // 第一个出现问题的节点，为pre 如 3 -> 2 -> 1， 第一个出现问题的节点first应该为pre节点3
        if(first == null && root.val < pre.val){
            first = pre;
        }
        // 第二个出现问题的节点， 为node 如3 -> 2 -> 1, 第二个出现问题的节点second应该为node节点 1
        if(first != null && root.val < pre.val){
            second = root;
        }
        // 更新pre
        pre = root;
        dfs(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