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

前言

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

一、力扣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 的话说明自己是 successorsuccessor = 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.valreturn inorderSuccessor(root.right, p);}
}

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

class Solution {public Node inorderSuccessor(Node node) {// 右子树的最小值就是 successorNode 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;}
}