删除节点：
LC669 修剪二叉搜索树
 LC450 删除二叉搜索树中的节点

根据有序数组生成BST：
⭕LC108 有序数组生成BBST[2]
LC109 有序链表生成BBST
⭕LC95 生成所有BST[2]（注意在空区间时，要返回vector<TreeNode*>{nullptr}）
⭕LC96 生成所有BST - 数量[2]
⭕LC654 生成最大的BST[1]

验证BST
⭕LC98 验证BST[2]这个题会用INT32_MIN来测试，所以我们用INT64_MIN来记录上一个节点。
⭕LC面试题33 二叉搜索树的后续遍历序列
⚠️LC255 验证前序遍历序列二叉搜索树(单调栈)

二叉搜索树展成链表：
⚠️LC426 BST展开为双向链表
⭕LC114 BST展开为单向链表

二差搜索树的后继节点：
LC173 二叉搜索树迭代器 hasNext()的条件
⚠️LC285 Inorder Successor in BST没有双亲节点指针
⭕LC510 Inorder Successor in BST II有双亲节点指针

⭕LC230 Kth Smallest Element in a BST
LC272 最接近的二叉搜索树值II

⭕LC99 恢复二叉搜索树[2]没有INT32_MIN这种坑
⭕️LC538 把二叉搜索树转变为累加树[1]
⚠️LC501 二叉搜索树中的众数[1]

BST节点的删除

LC669 修建二叉搜索树

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中。

如果一个节点<L，则这个节点和他的左子树都将被裁掉。在他的右子树上递归调用。
如果一个节点>R，则这个节点个他的右子树都将被裁掉。在他的左子树上递归调用。
如果节点属于[L, R]，在他的左右子树上递归调用。

code

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if(!root) return nullptr;
        // if the root is less than L, then the root itself and all the nodes in its left subtree will be discarded
        if(root->val < L) return trimBST(root->right, L, R);
        // if the root is greater than R, then the root itself and all the nodes in its right subtree will be discarded
        if(root->val > R) return trimBST(root->left, L, R);
        // if the root is in [L, R], then call trim on its left and right subtree recursively.
        root->left = trimBST(root->left, L, R);
        root->right= trimBST(root->right,L, R);
        return root;
    }
};

LC450 删除二叉搜索树中的节点

因为没有指向父节点的指针，为了简化逻辑，必须采用递归的方式来进行。通过递归函数的返回值来重置父节点中指向孩子节点的指针。

首先我们根据二叉搜索树的性质找到该节点
如果该节点没有孩子，则直接返回nullptr即可。
如果该节点有孩子，为了保证二叉搜索树的性质，需要将该节点的值和其【前序】/【后继】节点的值交换。交换后，在其【前序】/【后继】节点对应的子树上再递归地删除有对应值的节点。该节点最终一定会被移动到叶子节点上。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* predecessor(TreeNode* root)
    {
        root = root->left;
        while(root && root->right)
        {
            root = root->right;
        }
        return root;
    }

    TreeNode* successor(TreeNode* root)
    {
        root = root->right;
        while(root && root->left)
        {
            root = root->left;
        }
        return root;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root)
        {
            return nullptr;
        }
        else if(key < root->val)
        {
            root->left = deleteNode(root->left, key);
        }
        else if(key > root->val)
        {
            root->right = deleteNode(root->right, key);
        }
        else
        {
            if(!root->left && !root->right)
            {
                return nullptr;
            }

            if(root->right)
            {
                auto suc = successor(root);
                swap(suc->val, root->val);
                root->right = deleteNode(root->right, key);
            }
            else
            {
                auto pre = predecessor(root);
                swap(pre->val, root->val);
                root->left = deleteNode(root->left, key);
            }
        }

        return root;
    }
};

从有序数组构造二叉搜索树

排序数组转为平衡二叉搜素树

LC108 将有序数组转换为二叉搜索树

不加证明的给出以下结论：如果我们每次都选择区间的中点来作为根节点，那么构造出来的二叉树必然是平衡的。
思路：

- 选择区间中点，构造根节点
- 对左侧区间递归调用
- 对右侧区间递归调用
- 将构造的根节点，和递归调用的结果（左右子树）连接起来。
- 递归终止条件：区间为空。返回一个空指针即可。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums.begin(), nums.end());
    }
    template<typename It>
    TreeNode* sortedArrayToBST(It first, It last)
    {
        if(!(first < last)) return nullptr;
        auto mid = first + (last - first) / 2;
        auto leftTree = sortedArrayToBST(first, mid);
        auto rightTree = sortedArrayToBST(mid + 1, last);
        auto curTreeNode = new TreeNode{*mid};
        curTreeNode->left = leftTree;
        curTreeNode->right = rightTree;
        return curTreeNode;
    }
};

LC109 有序链表转换二叉搜索树

解法一：遍历链表转换为可以随机访问的数组，用前一题的解法即可。

code

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        auto list = vector<int>{};
        // copy the linked list into an array
        while(head)
        {
            list.push_back(head->val);
            head = head->next;
        }

        return toBST(list.begin(), list.end());
    }

    template<typename It>
    TreeNode* toBST(It first, It last)
    {
        if(!(first < last))
        {
            return nullptr;
        }

        auto mid = first + (last - first) / 2;
        auto root = new TreeNode{*mid};
        root->left = toBST(first, mid);
        root->right = toBST(mid + 1, last);
        return root;
    }
};

解法二：二叉搜索树的中序遍历序列有序。先计算链表长度。为保证二叉搜索树平衡，仍选择区间中点作为根节点。模拟中序遍历，在链表上不断移动head指针。

code

class Solution {
private:
    ListNode* hd;
public:
    TreeNode* sortedListToBST(ListNode* head) {
        size_t end = 0;
        hd = head;
        while(head)
        {
            ++end;
            head = head->next;
        }

        return toBST(0, end);
    }

    TreeNode* toBST(size_t first, size_t last)
    {
        if(!(first < last)) return nullptr;
        auto mid = first + (last - first) / 2;
        auto left = toBST(first, mid);

        // inorder traversal
        auto root = new TreeNode{hd->val};
        // move head to next.
        hd = hd->next;

        auto right = toBST(mid + 1, last);

        root->left = left;
        root->right = right;

        return root;

    }
};

最大二叉树

LC654 最大二叉树

思路同上，只不过是将区间中点换成了区间中的最大值。

code

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return constructMaximumBinaryTree(nums.begin(), nums.end());
    }
    template<typename It>
    TreeNode* constructMaximumBinaryTree(It first, It last)
    {
        if(!(first < last)) return nullptr;

        auto rootIt = max_element(first, last);

        auto leftTree = constructMaximumBinaryTree(first, rootIt);
        auto rightTree = constructMaximumBinaryTree(rootIt + 1, last);

        auto root = new TreeNode{*rootIt};
        root->left  = leftTree;
        root->right = rightTree;
        return root;
    }
};

生成给定区间所有的二叉搜索树

LC95 不同的二叉搜索树II

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。根据搜索树的性质，一个节点的左子树中的所有元素都比该节点小，一个节点的右子树中的所有元素都比该节点大。那么如果我们选1作为根节点，[2 … n]只能作为他的右子树。如果我们选择k < n作为根节点，[1 … k - 1]只能作为他的左子树，[k+1 … n]只能作为他的右子树。那么我们再在他的左右区间递归调用这个函数，就可以生成所有的二叉搜索树了。

generateTrees(first, last)

递归终止条件：[first, last)区间为空，即!(first < last)，这时返回一个只包含nullptr的集合
选择第i个节点作为根节点
- 生成所有可能的左子树集合：generateTrees(first, i)
- 生成所有可能的右子树集合：generateTrees(i+1, last)
遍历所有可能的左子树，右子树组合。对于每个组合
- 生成一个当前的根节点
- 将左右子树连接上去
- 把这个根节点加入结果集合
返回结果集合

更清晰的版本

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0) return {};
        return backtrack(1, n + 1);
    }

    vector<TreeNode*> backtrack(int first, int last)
    {
        if(first == last) return {nullptr};

        auto trees= vector<TreeNode*>{};

        for(int i = first; i < last; ++i)
            for(auto left : backtrack(first, i))
                for(auto right : backtrack(i + 1, last))
                {
                    trees.emplace_back(new TreeNode{i});
                    trees.back()->left  = left;
                    trees.back()->right = right; 
                }

        return trees;
    }
};

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0) return {};
        return generateTrees(1, n + 1);
    }

    vector<TreeNode*> generateTrees(int first, int last)
    {
        // recursion stop condition
        // if first == last, the range is empty, just push a
        // nullptr into the trees vector.
        if(!(first < last)) return {nullptr};
        
        auto trees = vector<TreeNode*>{};
        // pick up a node to be the root
        for(int i = first; i < last; ++i)
        {
            auto leftTrees  = generateTrees(first, i);
            auto rightTrees = generateTrees(i + 1, last); 

            // build trees
            for(auto leftRoot : leftTrees)
            {
                for(auto rightRoot : rightTrees)
                {
                    auto curTree = new TreeNode{i};
                    curTree->left  = leftRoot;
                    curTree->right = rightRoot;
                    trees.push_back(curTree);
                }
            }
        }

        return trees;

    }
};

求数量：LC96 不同的二叉搜索树

求数量如果还采用上面的递归方法会TLE。见数学类问题#卡塔兰数

递归TLE code

class Solution {
public:
    int numTrees(int n) {
        return numTrees(1, n + 1);
    }

    int numTrees(int first, int last)
    {
        // recursion stop condition
        // the range is empty, we can build no tree from it
        if(!(first < last)) return 1;


        auto curNums = 0;
        // pick a node as root
        for(int i = first; i < last; ++i)
        {
            auto leftNums  = numTrees(first, i);
            auto rightNums = numTrees(i + 1, last);

            curNums += leftNums * rightNums;
        }

        return curNums;
        
    }
};

验证BST

验证BST本体

LC98 Validate Binary Search Tree
思路：这个题不能简单的通过前序遍历递归判断一个节点是否大于左孩子 && 小于右孩子。二叉搜索树要求一个节点的右子树的所有节点都比该节点大，一个节点的左孩子的所有节点都比该节点小。不是简单的和【左孩子】【右孩子】的关系。正确的思路：中序遍历，记录前值，比较大小，如果后面的数不比前面大，二叉搜索树不正确。这个题坑比较多，前值不能简单的初始化设置成INT_MIN，因为他测试用例里有INT_MIN。所以得设置个isFirstElement的flag来判断前值是否已经设置好。或者用容量更大的int64_t，省去很多流程控制语句。

优化：因为递归调用的过程总是需要一次又一次传引用，我们考虑使用循环遍历的方法。

使用栈的循环遍历

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<TreeNode*> stack{};
        int64_t pre = INT64_MIN;
        bool     res = true;

        while(true)
        {
            while(root)
            {
                stack.push_back(root);
                root = root->left;
            }
            if(stack.empty()) break;
            root = stack.back();
            stack.pop_back();
            
            res = res && (root->val > pre);
            pre = root->val;
            root = root->right;            
        } 

        return res;
    }

};

传引用的方式

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        int64_t  pre = INT64_MIN;
        bool res = true;
        isValidBST(root, pre, res);
        return res;

    }

    void isValidBST(TreeNode* root, int64_t& pre, bool& res)
    {
        if(!root) return;
        isValidBST(root->left, pre, res);
        res = res && root->val > pre;
        pre = root->val;
        isValidBST(root->right, pre, res);
    }
};

验证BST后续遍历序列

AcWing46 二叉搜索树的后序遍历序列
 LC面试题33 二叉搜索树的后续遍历序列
解法一：使用递归的分治法

回忆后序遍历的特点：

根节点一定在最后
遍历序列当中的数可以被根节点partition成两部分，每一部分都是一个二叉搜索树。再递归判断这两部分是否是二叉搜索树。

复杂度分析

最差为$T(n) = T(n - a) + T(a) + \Theta(n) \Rightarrow O(n^2)$的时间复杂度。
如果该序列为平衡二叉树生成的后序遍历序列，使用主定理，为$T(n) = 2T(n/2) + \Theta(n) \Rightarrow O(n\log {n})$的时间复杂度。
空间复杂度为$O(1)$

2020.6.18 code

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return is_bbst(postorder.begin(), postorder.end());
    }

    template<typename It>
    auto is_bbst(It first, It last) -> bool
    {
        if(!(first < last))
        {
            return true;
        }

        auto back = *(last - 1);
        auto cmp = [back](auto x){return x < back;};
        if(is_partitioned(first, last, cmp))
        {
            auto point = partition_point(first, last, cmp);
            return is_bbst(first, point) && is_bbst(point, last - 1);
        }

        return false;   
    }
};

code

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return verifyPostorder(postorder.begin(), postorder.end());
    }
    template<typename It>
    bool verifyPostorder(It first, It last)
    {
        //range is empty, nothing to check
        if(!(first < last)) return true;
        // postorder traversal squence must be partitioned by the 
        // last element.
        --last;
        auto last_val = *last;
        auto cmp = [&last_val](auto x){ return x < last_val;};
        if(!is_partitioned(first, last, cmp)) return false;
        // find the partition point, the sequence could then be seperated 
        // into its left and right subtrees' postorder traversal sequence
        auto leftTreeLast = partition_point(first, last, cmp);
        return verifyPostorder(first, leftTreeLast) 
            && verifyPostorder(leftTreeLast, last);
    }
};

class Solution {
public:
    bool verifySequenceOfBST(vector<int> sequence) {
        if(sequence.empty() || sequence.size() <= 2) return true; 
        return _verifySequenceOfBSTImpl(sequence.begin(), sequence.end());
    }
    template<typename It>
    bool _verifySequenceOfBSTImpl(It first, It last){      
        if(distance(first, last)<=2) return true;
        auto back = last - 1;
        auto cmp = [&back](int x){return x<*back;};
        if(is_partitioned(first, last, cmp)){
            auto x = partition_point(first, last, cmp);//O(log(n))
            return _verifySequenceOfBSTImpl(first, x) 
                   && _verifySequenceOfBSTImpl(x, last - 1);
        }else return false;

    }
};

解法二：使用循环的方法

思路：每次检查数组最后一个数字是否能将前面的数组partition，如果能，去掉最后一个数，再重新检查，直到数组长度为1。

原理：后序遍历序列中，树的根节点位于整个序列最后，原理同解法一。去掉树的根节点后，最后的节点为该二叉搜索树的右子树的根节点。该节点的值必然大于左子树中任一节点的值。考虑右子树的后序遍历序列中，前一半为比右子树根节点小的，后一半是大于等于右子树根节点的。左子树中任一节点值都比右子树根节点小，将左子树的后序遍历序列贴在右子树的后序遍历序列前面，则该序列仍然能比右子树的根节点partition。

复杂度分析
时间复杂度:$\Theta(n^2)$
空间复杂度:$O(1)$

2020.6.18 code

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        for(auto first = postorder.begin(), last = postorder.end();
            first < last;
            --last)
        {
            if(!is_partitioned(first, last, 
                [back = *(last - 1)](auto x){return x < back;}))
            {
                return false;
            }
        }
        return true;
    }
};

code

class Solution {
public:
    bool verifySequenceOfBST(vector<int> sequence) {
        if(sequence.empty() || sequence.size() <= 2) return true; 
        auto first = sequence.begin();
        auto last  = sequence.end();
        while(last != first){
            if(!is_partitioned(first,--last, [&last](int x){return x<*last;})) return false;
        }
        return true;
    }
};

验证BST前序遍历序列

LC255 二叉搜索树的前序遍历序列

解法1：类似上一题，不断的用数组头去检查能否partition后面的区间。或递归检查也可。

code

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        auto it = preorder.begin();
        auto last = preorder.end();

        while(it < last)
        {
            auto val = *it;
            if(!is_partitioned(++it, last, [val](auto x){return x < val;})) return false;
        }

        return true;
    }
};

参考：
单调栈校验BST前序遍历

还是有点不太理解原因。维护一个单调栈，并要求待入栈的节点 > 从栈中出来的所有节点。

code

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        vector<int> monoStack{};
        auto min = INT_MIN;
        for(auto val : preorder)
        {
            if(val < min) return false;
            while(!monoStack.empty() && val > monoStack.back())
            {
                min = monoStack.back();
                monoStack.pop_back();
            }
            monoStack.push_back(val);
        }
        return true;
    }
};

BST与链表

BST展开为双向链表

剑指Offer 36, LC426 Convert Binary Search Tree to Sorted Doubly Linked List, AcWing 49

只需要中序遍历，记录上一个节点指针，并连接即可。最后我们还需要把第一个节点和最后一个节点连接起来。第一个节点可以在第一次访问节点时记录，最后一个节点自然就是遍历完成后的”上一个指针”，将他俩连接起来即可。

code

class Solution {
private:
    Node* first;
    Node* last;   
public:
    Solution()
    :first(nullptr)
    ,last(nullptr)
    {}

    Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        treeToDoublyList_(root);
        last->right = first;
        first->left = last;

        auto head = first;

        //clear the state
        first = nullptr;
        last  = nullptr;

        return head;
    }

    void treeToDoublyList_(Node* root)
    {
        if(!root) return;
        treeToDoublyList_(root->left);
        // if last is nullptr then this is the first node in the traversal
        if(!last)
        {
            //set first
            first = root;
        }
        else
        {
            // link root with the last node
            root->left  = last;
            last->right = root;
        }

        last = root;
        treeToDoublyList_(root->right);
    }
};

2019年8月的思路

思考Morris中序遍历，会自动将节点和其前序节点连接起来。如果我们在遍历后不恢复right指针，而且在每次访问的时候，都记录上一次访问的节点的指针pre。这个指针用nullptr初始化。每次访问时，将上一次访问的节点的指针pre的right设置成这次访问的节点root，这次访问的节点root的left设置成pre即可。

而且【将上一次访问的节点的指针pre的right设置成这次访问的节点root】这个事情只需要在root->left == nullptr的时候做，否则是多余的。原因：TODO

class Solution {
public:
    TreeNode* convert(TreeNode* root) {
        auto head = static_cast<TreeNode*>(nullptr);
        auto pre = static_cast<TreeNode*>(nullptr);
        while(root){
            if(!root->left){
                if(pre) pre->right = root;
                else head = root;
                root->left = pre;
                pre = root;
                root = root->right;
            }else{
                auto findpre = root->left;
                while(findpre->right && findpre->right != root) findpre = findpre->right;
                if(findpre->right == nullptr){
                    findpre->right = root;
                    root = root->left;
                }else{
                    root->left = pre;
                    pre = root;                    
                    root = root->right;
                }
            }
        }
        return head;
    }
};

BST展开成单向链表

LC114 Flatten Binary Tree to Linked List

思路：

如果没有左子树，就进入右子树
如果有左子树，就把右子树换成左子树。然后将右子树连接在交换后的右子树的最右节点处。
不断检查，直到没有右子树

code

class Solution {
public:
    void flatten(TreeNode* root) {
        while(root)
        {
            // if there is no left subtree, continue to check its
            // right subtree
            if(!root->left) 
            {
                root = root->right;
                continue;
            }

            // replace its right subtree with its left subtree
            auto right = root->right;
            root->right = root->left;
            root->left  = nullptr;

            auto new_root = root->right;
            
            // move right to the end
            while(root->right)
            {
                root = root->right;
            }

            // attach its right subtree there
            root->right = right;

            // update the root
            root = new_root;
        }
    }
};

二叉搜索树的第k小节点

剑指Offer 54, LC230 Kth Smallest Element in a BST
思路就是二叉搜索树的中序遍历序列就是按顺序输出。
不推荐的办法：Morris遍历。Morris遍历不能中途退出！！，如果中途退出，会使破坏树的结构。

Morris

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        auto result = 0;
        while(root){
            if(!root->left){
                --k;
                if(k == 0) result = root->val;

                root = root->right;
            }else{
                auto pre = root->left;
                while(pre->right && pre->right != root) pre = pre->right;
                if(pre->right == nullptr){
                    pre->right = root;
                    root = root->left;
                }else{
                    --k;
                    if(k == 0) result = root->val;
                    pre->right = nullptr;
                    root = root->right;
                }
            }
        }
        return result;
    }
};

Stack

最接近的二叉搜索树值

LC272 最接近的二叉搜索树值II

使用一个大小为k的priority_queue，遍历所有的节点即可。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    size_t m_k;
    double m_target;

    auto compare(int lhs, int rhs) -> bool
    {
        return abs(m_target - lhs) < abs(m_target - rhs);
    }
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        m_k = k;
        m_target = target;
        auto cmp = [this](auto lhs, auto rhs)
        {
            return compare(lhs, rhs);
        };
        auto pq = priority_queue<int, vector<int>, decltype(cmp)>{cmp};
        traverse(root, pq);
        auto res = vector<int>{};
        while(!pq.empty())
        {
            res.push_back(pq.top());
            pq.pop();
        }

        return res;
    }

    template<typename PQ>
    void traverse(TreeNode* root, PQ& pq)
    {
        if(!root)
        {
            return;
        }

        if(pq.size() < m_k
        || (compare(root->val, pq.top())))
        {
            pq.push(root->val);
        }

        if(pq.size() > m_k)
        {
            pq.pop();
        }

        traverse(root->left, pq);
        traverse(root->right, pq);
    }
};

BST后继节点

LC173 二叉搜索树迭代器

提供一个二差搜索树的根节点。构建一个二差搜索树的向前迭代器。我们可以改造用stack中序遍历二差搜索树的代码。将大循环拆开。

stack-inorder-traversal code

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res{};
        vector<TreeNode*> stack{};
        
        while(true)
        {
            while(root)
            {
                stack.push_back(root);
                root = root->left;
            }
            
            if(stack.empty()) break;
            
            root = stack.back();
            // #1
            stack.pop_back();
            res.push_back(root->val);
            root = root->right;
        }

        return res;
    }
};

code

class BSTIterator {
private:
    stack<TreeNode*> m_stack;
    TreeNode* m_root;
public:
    BSTIterator(TreeNode* root)
    :m_stack{}
    ,m_root{root}
    {}
    
    /** @return the next smallest number */
    int next() {
        return inorder()->val;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return m_root || !m_stack.empty();
    }

    auto inorder() -> TreeNode*
    {
        while(m_root)
        {
            m_stack.push(m_root);
            m_root = m_root->left;
        }

        if(m_stack.empty())
        {
            return m_root;
        }

        m_root = m_stack.top();
        m_stack.pop();

        auto res = m_root;
        m_root = m_root->right;

        return res;
    }
};

注意这里hasNext()的判断条件不仅仅是!stack.empty()。因为当stack当中只有一个元素时，运行#1处的代码后，stack也会变空。因此hasNext()的判断条件应该是m_root || !m_stack.empty()。

LC285 Inorder Successor in BST, LC285 Inorder Successor in BST II, 剑指Offer 8, AcWing19 二叉树的下一个节点

一个节点的【后继节点】是：

如果这个节点的右子树非空，【后继节点】是右子树中的最小节点（右子树中一直沿着左走到头）
如果这个节点的右子树是空的，【后继节点】就是第一个把该节点当作左孩子的祖先节点（有可能不存在）。

一个节点的【前序节点】是：

如果这个节点的左子树非空，【前序节点】就是左子树中的最大节点（左子树中一直沿着右走到头）
如果这个节点的左子树是空的,【前序节点】就是第一个把该节点当作右孩子的祖先节点（有可能不存在）。

当有parent指针的时候，如果节点右子树为空，我们很容易通过父亲节点找到他的后继。
LC285 Inorder Successor in BST II

有parent节点指针的解法

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        if(!node) return nullptr;
        // if the node has a right ptr
        // we have to find the smallest node in its
        // right subtree
        if(node->right)
        {
            node = node->right;
            while(node->left) node = node->left;
            return node;
        }

        // if the node has no right ptr
        // we have to find the first node that takes it as
        // left child.
        auto parent = node->parent;
        // if there is no such node, parent will move to the 
        // parent of the root, which is nullptr, thus no worry
        while(parent && parent->left != node)
        {
            node = parent;
            parent = parent->parent;
        }
        return parent;
    }
};

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if(p->right){
            p = p->right;
            while(p->left) p = p->left;
            return p;
        }else{
            while(p){
                auto father = p->father;
                if(father && father->left == p) return father;
                p = father;
            }
            return p;
        }
    }
};

LC285 Inorder Successor in BST

当没有parent指针的时候，我们只能靠改节点的值，从头遍历来找到该节点的后继。将当前节点称为cur，从根节点开始cur = root，初始化res = nullptr

循环直到cur == nullptr：
- 如果cur < p，向左走cur = cur->left并记录备份下res = cur。
- 否则cur = cur->right
  可以自己用一个二叉搜索树试一下，会发现这段程序包括了所有的情况：
- 右子树非空
- 右子树为空，且是最后一个节点。
- 右子树为空，但不是最后一个节点。

code

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* suc = nullptr;
        while(root)
        {
            
            if(p->val < root->val)
            {
                suc = root;
                root = root->left;
            }
            else
            {
                root = root->right;
            }
        }
        return suc;
    }
};

恢复二叉搜索树

LC99 恢复二叉搜索树

思路：
中序遍历二叉搜索树，记录前一个node的值，寻找中序遍历中的逆序。如果发现pre比cur大，就把pre和cur都记录到数组中。

如果这两个被错误交换的节点在中序遍历序列中是紧挨着的，那么最后会找到一对这样的pre和cur [pre, cur]
如果不是挨着的，那么就会找到2对这样的pre和cur。[pre1, cur1, pre2, cur2]
无论找到几个，只需要把这个数组的头和尾node的值交换即可。

使用stack循环中序遍历的code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        auto s = stack<TreeNode*>{};
        auto inversion = vector<TreeNode*>{};
        TreeNode* pre = nullptr;

        while(true)
        {
          while(root)
          {
            s.push(root);
            root = root->left;
          }

          if(s.empty())
          {
            break;
          }

          root = s.top();
          s.pop();

          if(pre && pre->val > root->val)
          {
            inversion.push_back(pre);
            inversion.push_back(root);
          }

          pre = root;
          root = root->right;
        }

        swap(inversion.front()->val, inversion.back()->val);
    }
};

没有用Morris遍历的code

class Solution {
public:
    void recoverTree(TreeNode* root) {
        vector<TreeNode*> inversions{};
        vector<TreeNode*> stack{};
        TreeNode dummy = TreeNode{INT_MIN};
        TreeNode* pre  = &dummy;

        // do inorder traversal on the tree
        while(true)
        {
            while(root)
            {
                stack.push_back(root);
                root = root->left;
            }
            if(stack.empty()) break;
            root = stack.back();
            stack.pop_back();
            // check if it is an inversion
            if(pre->val > root->val)
            {
                // log the inversions
                inversions.push_back(pre);
                inversions.push_back(root);
            }
            pre = root;
            root = root->right;
        }

        // swap their value
        auto tmp = inversions.front()->val;
        inversions.front()->val = inversions.back()->val;
        inversions.back()->val = tmp;
    }
};

二叉搜索树转变为累加树

LC538 把二叉搜索树转变为累加树
要求：每个节点的值是原来的节点值加上所有大于它的节点值之和。
思路：做一个反向的中序遍历（right, root, left），不断累加节点的值即可。

code

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        auto root_copy = root;
        vector<TreeNode*> stack{};
        auto sum = 0;
        // do a inverse inorder traversal
        while(true)
        {
            while(root)
            {
                stack.push_back(root);
                root = root->right;
            }

            if(stack.empty()) break;
            root = stack.back();
            stack.pop_back();
            root->val += sum;
            sum = root->val;
            root = root->left;
        }

        return root_copy;
    }
};

二叉搜索树中的众数

LC501 二叉搜索树中的众树
中序遍历即可，所有相等的值必然集中在一起。

code

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res{};
        vector<TreeNode*> stack{};
        auto isFirstValue = true;
        auto val = 0;
        auto cnt = 0;
        auto max_cnt = 0;
        while(true)
        {
            while(root)
            {
                stack.push_back(root);
                root = root->left;
            }            

            if(stack.empty()) break;

            root = stack.back();
            stack.pop_back();

            // if it is the first value in the tree
            if(isFirstValue)
            {
                val = root->val;
                cnt = 1;
                max_cnt = 1;
                isFirstValue = false;
            }
            // check if same value
            else if(root->val == val)
            {
                ++cnt;
            }
            else if(root->val != val)
            {
                //reset the counter
                val = root->val;
                cnt = 1;
            }

            // check if the counter == max_cnt
            if(cnt == max_cnt)
            {
                res.push_back(root->val);
            }
            // we find a new max_count, clear the result
            else if(cnt > max_cnt)
            {
                // update max_cnt
                max_cnt = cnt;
                // clear the res, we do not need them anymore
                res.clear();
                // the new max
                res.push_back(root->val);
            }

            root = root->right;
        }
        return res;
    }
};

LC530 二叉搜索树的最小绝对差
最小绝对差一定发生在中序遍历序列中两个相邻的数之间，中序遍历即可。

code

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<TreeNode*> stack{};
        auto isFirstValue = true;
        int val  = 0;
        int diff = INT_MAX; 
        // do an inorder traversal
        while(true)
        {
            while(root)
            {
                stack.push_back(root);
                root = root->left;
            }

            if(stack.empty()) break;

            root = stack.back();
            stack.pop_back();

            if(isFirstValue)
            {
                val = root->val;
                isFirstValue = false;
            }
            else
            {
                diff = min(diff, abs(root->val - val));
                val  = root->val;
            }

            root = root->right;
        }

        return diff;
    }
};