提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「遍历」的思维模式。
一、力扣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;
}
}
