🌕 99. 恢复二叉搜索树

难度: 🌕

问题描述

---

解法

/**
 * 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;
 *     }
 * }
 */
class Solution {
    TreeNode a = null;
    TreeNode b = null;
    TreeNode pre = null;
    public void recoverTree(TreeNode root) {
        // 思路：
        // 中序遍历 - 二叉搜索树有序
        // 遇到初个降序的数，记为 a
        // 继续往后遍历，找到首个 ?.val > a.val 
        // ? 前面的节点就是 第二个数，记为 b
        mySol(root);
        if(a == null) {
            a = root;
        }
        if(b == null) {
            b = pre;
        }
        // System.out.println(a.val + "  " + b.val);
        int tmp = a.val;
        a.val = b.val;
        b.val = tmp;
    }

    private void mySol(TreeNode root) {
        // 递归终止条件
        if(root == null) {
            return;
        }
        if(a != null && b != null) {
            return;
        }
        // root != null
        mySol(root.left);
        if(a != null && b != null) {
            return;
        }
        // 单层递归逻辑
        TreeNode cur = root;
        System.out.println(cur.val);
        if(pre != null && cur.val < pre.val) {
            // 判断是第一个还是第二个
            if(a == null) {
                a = pre;
            } else {
                b = cur;
                return;
            }
        } 
        if(a != null && cur.val > a.val) {
            b = pre;
            return;
        }
        pre = cur;
        mySol(root.right);
    }
}

---

输出