力扣labuladong——一刷day68

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「遍历」的思维模式。

一、力扣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 pre = null, first = null, second = null;
    public void recoverTree(TreeNode root) {
        fun(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
    public void fun(TreeNode root){
        if(root == null){
            return;
        }
        fun(root.left);
        if(pre != null && root.val < pre.val){
            if(first == null){
                first = pre;
            }
                second = root;
        }
        pre = root;
        fun(root.right);
    }
}

二、力扣285.二叉搜索树中的中序后继

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) {
            return null;
        }

        TreeNode successor = null;

        if (root.val > p.val) {
            // 父节点收到 null 的话说明自己是 successor
            successor = inorderSuccessor(root.left, p);
            if (successor == null) {
                successor = root;
            }
        }
        if (root.val < p.val) {
            successor = inorderSuccessor(root.right, p);
        }

        if (root.val == p.val) {
            // 我是目标节点，我的 successor 要么是右子树的最小节点，要么是父节点
            successor = getMinNode(root.right);
        }

        return successor;
    }

    // BST 中最左侧的节点就是最小节点
    private TreeNode getMinNode(TreeNode p) {
        while (p != null && p.left != null) {
            p = p.left;
        }
        return p;
    }

    // 精简代码装逼版解法
    public TreeNode inorderSuccessor_Opt(TreeNode root, TreeNode p) {
        if (root == null) {
            return null;
        }

        if (root.val > p.val) {
            TreeNode successor = inorderSuccessor(root.left, p);
            return successor == null ? root : successor;
        }
        // root.val == p.val || root.val < p.val
        return inorderSuccessor(root.right, p);
    }
}

三、力扣510.二叉搜索树中的中序后继II

class Solution {
    public Node inorderSuccessor(Node node) {
        // 右子树的最小值就是 successor
        Node p = node.right;
        while (p != null && p.left != null) {
            p = p.left;
        }
        if (p != null) {
            return p;
        }
        // 没有右子树的话，第一个比自己大的父节点就是 successor。
        // 但是 p 可能是父节点的左子节点也可能是右子节点，
        // 只有 p 是左子节点的时候父节点才是 successor。
        p = node;
        while (p.parent != null && p.parent.right == p) {
            p = p.parent;
        }
        return p.parent;
    }
}