236. 二叉树的最近公共祖先
 
 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
 最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

 示例 1:
 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 输出: 3
 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
 
 示例 2:
 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 输出: 5
 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
  
 说明:
 所有节点的值都是唯一的。
 p、q 为不同节点且均存在于给定的二叉树中

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    
    /**
      * 去以root为根节点的二叉树中查找p、q的最近公共祖先
      * ① 如果p、q同时存在于这棵二叉树中，就能成功返回它们的最近公共祖先
      * ② 如果p、q都不存在于这棵二叉树中，返回null
      * ③ 如果只有p存在于这棵二叉树中，返回p
      * ④ 如果只有q存在于这棵二叉树中，返回q
      */
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if (root == nullptr || root == p || root == q) return root;
        
        // 去以root.left为根节点的二叉树中查找p、q的最近公共祖先
        TreeNode * left = lowestCommonAncestor(root->left, p, q);
        // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
        TreeNode * right = lowestCommonAncestor(root->right, p, q);
        
        if (left != nullptr && right != nullptr) return root;
        
        return (left != nullptr) ? left : right;
    }
};

99. 恢复二叉搜索树
 
 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
 
 示例 1：
 输入：root = [1,3,null,null,2]
 输出：[3,1,null,null,2]
 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
 
 
 示例 2：
 输入：root = [3,1,4,null,null,2]
 输出：[2,1,4,null,null,3]
 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
  

 提示：
 树上节点的数目在范围 [2, 1000] 内
 -231 <= Node.val <= 231 - 1

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/recover-binary-search-tree
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution1 {
public:
    //上一次中序遍历过的节点
    TreeNode * prev;
    //第一个错误节点
    TreeNode * first;
    //第二个错误节点
    TreeNode * second;
    
    void recoverTree(TreeNode* root) {
        //中序遍历查找错误节点
        inorder(root);
        
        //交换2个错误节点的值
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
    
    
    //中序遍历
    void inorder(TreeNode* root){
        if (root == nullptr) return;
        inorder(root->left);
        find(root);
        inorder(root->right);
    }
    
    
    //查找错误节点
    void find(TreeNode* node){
        //出现了逆序对
        if (prev != nullptr && prev->val > node->val) {
            //第二个错误节点：最后一个逆序对中较小的那个节点
            second = node;
            
            //第1个错误节点：第一个逆序对中较大的那个节点
            if (first != nullptr) return;
            first = prev;
        }
        prev = node;
    }
};

//morris方法遍历二叉树
class Solution {
public:
    //上一次中序遍历过的节点
    TreeNode * prev;
    //第一个错误节点
    TreeNode * first;
    //第二个错误节点
    TreeNode * second;
    
    void recoverTree(TreeNode* root) {
        //中序遍历查找错误节点
        morris(root);
        
        //交换2个错误节点的值
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
    
    
    //中序遍历
    void morris(TreeNode* root){
        TreeNode * node = root;
        
        while (node != nullptr) {
            if (node->left !=nullptr) {
                
                // 找到前驱节点(predecessor)、后继节点(successor)
                TreeNode * pred = node->left;
                while (pred->right != nullptr && pred->right != node) {
                    pred = pred->right;
                }
                
                if (pred->right == nullptr) {
                    pred->right = node;
                    node = node->left;
                } else { // pred.right == node
                    find(node);
                    pred->right = nullptr;
                    node = node->right;
                }
            }else{
                find(node);
                node = node->right;
            }
        }
    }
    
    
    //查找错误节点
    void find(TreeNode* node){
        //出现了逆序对
        if (prev != nullptr && prev->val > node->val) {
            //第二个错误节点：最后一个逆序对中较小的那个节点
            second = node;
            
            //第1个错误节点：第一个逆序对中较大的那个节点
            if (first != nullptr) return;
            first = prev;
        }
        prev = node;
    }
};

class Solution1 {
 
    bool isBST(TreeNode * root){
        return false;
    }
    
    
    int nodesCount(TreeNode * root){
        return 0;
    }
    
public:
    int largestBSTSubtree(TreeNode*root){
        if (root == nullptr) return 0;
        if (isBST(root)) return nodesCount(root);
        return max(largestBSTSubtree(root->left), largestBSTSubtree(root->right));
    }
};

class Solution {
    class Info{
    public:
        /** 根节点 */
        TreeNode* root;
        /** 节点总数 */
        int size;
        /** 最大值 */
        int max;
        /** 最小值 */
        int min;
        
        Info(TreeNode*root,int size,int max,int min){
            this->root = root;
            this->size = size;
            this->max = max;
            this->min = min;
        }
    };
    
    
    Info* getInfo(TreeNode* root){
        
        if (root == nullptr) return nullptr;
        
        // li(left info)：左子树的最大BST子树信息
        Info* li = getInfo(root->left);
        
        // ri(right info)：右子树的最大BST子树信息
        Info* ri = getInfo(root->right);
        
        /*
         有4种情况，以root为根节点的二叉树就是一棵BST，最大BST子树就是其本身
         ① li != null && ri != null
         && li.root == root.left && root.val > li.max
         && ri.root == root.right && root.val < ri.min
         
         ② li != null && ri == null
         && li.root == root.left && root.val > li.max
         
         ③ li == null && ri != null
         && ri.root == root.right && root.val < ri.min
         
         ④ li == null && ri == null
         */

        int leftBstSize = -1, rightBstSize = -1, max = root->val, min = root->val;
        
        if (li == nullptr) {
            leftBstSize = 0;
        } else if (li->root == root->left && root->val > li->max) {
            leftBstSize = li->size;
            min = li->min;
        }

        if (ri == nullptr) {
            rightBstSize = 0;
        } else if (ri->root == root->right && root->val < ri->min) {
            rightBstSize = ri->size;
            max = ri->max;
        }

        if (leftBstSize >= 0 && rightBstSize >= 0) {
            return new Info(root, 1 + leftBstSize + rightBstSize, max, min);
        }

        // 以root为根节点的二叉树并不是BST
        
        // 返回最大BST子树的节点数量较多的那个Info
        if (li != nullptr && ri != nullptr) return (li->size > ri->size) ? li : ri;
        
        // 返回li、ri中不为null的那个Info
        return (li != nullptr) ? li : ri;
    }
    
public:
    int largestBSTSubtree(TreeNode*root){
        return (root == nullptr) ? 0 : getInfo(root)->size;;
    }
};