Leetcode 刷题笔记

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}


int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

void traverse(cosnt int[]& arr){
    for(int i=0;i<arr.length;i++)
        // visit();
}

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val：迭代需要写出我们每个的具体操作
    }
}
// 两种不同的遍历写法👆 👇，具体思路上的区别
void traverse(ListNode head) {
    // 递归访问 head.val
    // 递归是基于我们的n-1假设，只需要实现n-1 到n的转变就行
    traverse(head.next);
}

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    // oprtator 前序遍历
    traverse(root.left);
    // oprtator 中序遍历
    traverse(root.right);
    // oprtator 后序遍历
}

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n = nums2.size();
        unordered_map<int,int>orderh; // 这个没有长度初始化这种说法的
        stack<int> temps;
        vector<int> res; // 只初始化长度的话，会初始化为0；
        temps.push(nums2[0]);
        // 当遇到比原本的大的时候，我们就直接弹出，直到里面的都比他大
        for(int i =1; i<n; i++){
            while(!temps.empty() && nums2[i]>temps.top()){
                orderh[temps.top()] = nums2[i];
                temps.pop();
            }
            temps.push(nums2[i]);
        }
        // 对于剩下来的哪些元素，就赋值为-1
        while(!temps.empty()){
            orderh[temps.top()] = -1;
            temps.pop();
        }
        // 添加进最终的结果。
        for(int num: nums1){
            res.push_back(orderh[num]);
        }
        return res;

    }
};

vector<int> dailyTemperatures(vector<int>& T) {
    vector<int> res(T.size());
    // 这里放元素索引，而不是元素
    stack<int> s; 
    /* 单调栈模板 */
    for (int i = T.size() - 1; i >= 0; i--) {
        while (!s.empty() && T[s.top()] <= T[i]) {
            s.pop();
        }
        // 得到索引间距
        res[i] = s.empty() ? 0 : (s.top() - i); 
        // 将索引入栈，而不是元素
        s.push(i); 
    }
    return res;
}

int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
    print(arr[index % n]);
    index++;
}

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        stack<int> s;
        // 假装这个数组长度翻倍了
        for (int i = 2 * n - 1; i >= 0; i--) {
            // 索引要求模，其他的和模板一样
            while (!s.empty() && s.top() <= nums[i % n])
                s.pop();
            res[i % n] = s.empty() ? -1 : s.top();
            s.push(nums[i % n]);
        }
        return res;
    }
};

class Solution {
public:
    string removeDuplicateLetters(string s) {
        if(s.empty()) return {};
        // 初始化需要的存储数据结构
        vector<int> countAl(256,0); 
        vector<bool> countSt(256,false);
        stack<int> store;
        // 初始化count数组
        for(auto t: s){
            countAl[t]++;
        }
        for(char c: s){
            countAl[c]--;
            if(countSt[c]) continue;
            while(!store.empty() && store.top()>c){
                // 如果top后面没有了
                if(countAl[store.top()]==0)
                    break;
                // 如果还有就pop
                countSt[store.top()] = false;
                store.pop();
            }
            store.push(c);
            countSt[c] = true;
        }
        // 对stack中的字符进行反转然后输出
        string res;
        stack<char> temp;
        while(!store.empty()){
            temp.push(store.top());
            store.pop();
        }
        while(!temp.empty()){
            res.push_back(temp.top());
            temp.pop();
        }
        return res;
    }
};

class RandomizedSet {
public:
    // 存储元素的值
    vector<int> nums;
    // 记录每个元素对应在 nums 中的索引
    unordered_map<int,int> valToIndex;

    bool insert(int val) {
        // 若 val 已存在，不用再插入
        if (valToIndex.count(val)) {
            return false;
        }
        // 若 val 不存在，插入到 nums 尾部，
        // 并记录 val 对应的索引值
        valToIndex[val] = nums.size();
        nums.push_back(val);
        return true;
    }

    bool remove(int val) {
        // 若 val 不存在，不用再删除
        if (!valToIndex.count(val)) {
            return false;
        }
        // 先拿到 val 的索引
        int index = valToIndex[val];
        // 将最后一个元素对应的索引修改为 index
        valToIndex[nums.back()] = index;
        // 交换 val 和最后一个元素
        swap(nums[index], nums.back());
        // 在数组中删除元素 val
        nums.pop_back();
        // 删除元素 val 对应的索引
        valToIndex.erase(val);
        return true;
    }

    int getRandom() {
        // 随机获取 nums 中的一个元素
        return nums[rand() % nums.size()];
    }
};

 跳过尾部的黑名单缩影的问题
int last = N - 1;
        for (int b : blacklist) {
            // 如果 b 已经在区间 [sz, N)
            // 可以直接忽略
            if (b >= sz) {
                continue;
            }
            while (mapping.count(last)) {
                last--;
            }
            mapping[b] = last;
            last--;
        }

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) { 
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;  // 这里也很重要！只有一个的时候return啥。
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

 */
class Solution 
{
private:
    ListNode* last = nullptr;
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == 1)
        {
            return reverseN(head, n);
        }
        head->next = reverseBetween(head->next, m - 1, n - 1);
        // 这里，return head和递归之间的关系要掌握好，从变换的阈值开始分析，比较传入值和return值就知道了
        return head;
    }
    ListNode* reverseN(ListNode* head, int n)
    {
        if (n == 1)
        {
            last = head->next;
            return head;
        }
        ListNode* tail = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = last;
        return tail;
    }
};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* start, *end;
        start = end = head;
        for (int i = 0; i<k;i++)
        {
            if(end == nullptr)
                return head;
            end = end->next;
        }
        ListNode* newH = reversek(start,end);
        start->next = reverseKGroup(end,k);
        return newH;
    }
    ListNode* reversek(ListNode* start, ListNode* end)
    {
        ListNode* curr = start; 
        ListNode* prev = nullptr; //最后的赋值再下一行，哪个start.net
        while(curr!=end)
        {
            ListNode* temp = curr;
            curr = curr->next;
            temp->next= prev;
            // curr.next= temp; 多做了一部，我们只做到当前curr指向的点就行
            prev = temp; 
        }
        return prev;
    }
};

时间和空间复杂度都是O（n）
    后续需要对这个方法进行优化
使用后续遍历的迭代思想进行的例子;
实现上的核心问题：我们虽然可以通过后序遍历来首先取到链表的tail;
但是我们如何让最底层的取到的也是最前面的head呢？（需要另一一个共有head）;
class Solution {
public:
    ListNode* head;
    bool isPalindrome(ListNode* head) {
        this->head = head;
        return reverseJ(head);
    }
    bool reverseJ(ListNode* tail){
        // 我们虽然可以通过后序遍历来首先取到链表的tail
        // 但是我们如何让最底层的取到的也是最前面的head呢？（需要另一一个共有head）
        if (tail == nullptr)
            return true;
        bool ans = reverseJ(tail->next);
        ans = ans && (this->head->val == tail->val);
        this->head = this->head->next;
        return ans;
    }
};

ListNode* slow, *fast;
slow = fast = head;
while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
}
if (fast != nullptr)
    slow = slow->next;
// slow 指针现在指向链表中点

//* Definition for a binary tree node.
class Solution {
private:
    int ans = INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        helpSum(root);
        return ans;
    }
    int helpSum(TreeNode* root)
    {
        if (root == nullptr)
            return 0;
        // 考虑negative的情况；用0来判断是否要输入
        int rightG = max(helpSum(root->right), 0);
        int leftG = max(helpSum(root->left), 0);
        // 不经过该节点的情况已经在子节点的地方输出了，不需要我自己画蛇添足的在这里进行政府的判断；
        // 从最低层节点开始分析你就知道了，已经包含在ans中了
        int temp = root->val + rightG + leftG;
        ans = max(temp,ans);
        // 最终都是复数的情况？可能还要考虑temp和val哪个更小的问题
        return max(rightG,leftG) + root->val;
    }
};

class Solution 
{
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        // int tempre[preorder.size()];
        // 函数，返回一个迭代器
        return helpbuild(preorder.begin(),preorder.end(),inorder.begin(),inorder.end());
    }
    // 学，给老子学，怎么在c++中实现动态数组的划分传入，如果是python可太爽了；
    TreeNode* helpbuild(vector<int>::iterator preb, vector<int>:: prend, \
        vector<int>::iterator inob, vector<int>::iterator inoe)
    {
        if(inob == inoe)
            return nullptr;
        TreeNode* cur = new TreeNode(*preb);
        // 记住这个函数find，返回的是一个迭代器，迭代器本身就是一个指针，指针的+1会随着类型的不同而变化
        auto root = std::find(inob,inoe,*preb);
        cur->left = helpbuild(preb+1,preb+(root-inob)+1,inob,root);
        cur->right = helpbuild(preb+(root-inob)+1,prend,root+1,inoe);

        return cur;
    }
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return helpbuild(inorder.begin(),inorder.end(),postorder.begin(),postorder.end());

    }
    TreeNode* helpbuild(vector<int>::iterator ins,vector<int>::iterator ine,
                        vector<int>::iterator pos, vector<int>::iterator poe)
    {
        if(poe == pos)
            return nullptr;
        // 这里要注意的是end是有值的下一项
        // iterator 之间的加减和index之间的加减的关系的转化也要清楚到底是怎么回事
        poe--;
        TreeNode* cur = new TreeNode(*poe);
        auto root = find(ins,ine,*poe);
        cur->left = helpbuild(ins,root,pos,poe-(ine-root-1));
        cur->right = helpbuild(root+1,ine,poe-(ine-root-1),poe);
        return cur;

    }
};

TreeNode build(int[] inorder, int inStart, int inEnd,
               int[] postorder, int postStart, int postEnd) {

    if (inStart > inEnd) {
        return null;
    }
    // root 节点对应的值就是后序遍历数组的最后一个元素
    int rootVal = postorder[postEnd];
    // rootVal 在中序遍历数组中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }
    // 左子树的节点个数
    int leftSize = index - inStart;
    TreeNode root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(inorder, inStart, index - 1,
                        postorder, postStart, postStart + leftSize - 1);

    root.right = build(inorder, index + 1, inEnd,
                        postorder, postStart + leftSize, postEnd - 1);
    return root;
}

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)
            return nullptr;
        TreeNode* Temp = root->right;
        root->right = root-> left;
        root->left = Temp;
        invertTree(root->right);
        invertTree(root->left);
        return root;
    }
};

class Solution {
public:
    Node* connect(Node* root) 
    {
        if(!root)
            return nullptr;
        else
        {
            Node* temptr = root;
            while(root != nullptr){
                // 这一步特别重要也容易忽略
                if(!root->left)
                    return temptr;
                root->left->next = root->right;
                root->right->next = root->next?root->next->left:nullptr;
                root = root->next;
            }
            connect(temptr->left);
            return temptr;
        }
    }
};

class Solution {
public:
    // 主函数
    Node* connect(Node* root) {
        if (root == nullptr) 
            return nullptr;
        connectTwoNode(root->left, root->right);
        return root;
    }

    // 辅助函数
    void connectTwoNode(Node* node1, Node* node2) {
        if (node1 == nullptr || node2 == nullptr) {
            return;
        }
        /**** 前序遍历位置 ****/
        // 将传入的两个节点连接
        node1->next = node2;

        // 连接相同父节点的两个子节点
        connectTwoNode(node1->left, node1->right);
        connectTwoNode(node2->left, node2->right);
        // 连接跨越父节点的两个子节点
        connectTwoNode(node1->right, node2->left);
    }
};

class Solution {
public:
    void flatten(TreeNode* root) {
        helpflat(root);
    }
    TreeNode* helpflat(TreeNode* root){
        // 递归的终点以及空值判断
        if(!root)
            return nullptr;
        //n-1假设：flaten后续的节点并变到左侧，同时由于后续的接入需求，我们需要return最后一个有值的节点
        TreeNode* lefte = helpflat(root->left);
        TreeNode* righte = helpflat(root->right);
        //加入最后左右都是0的话，我们就return当前节点而不是下一个节点（因为我们需要最后一个元素的索引），这其实也是终值判断
        if(!lefte && !righte)
            return root;
        // 如果只有右边无序处理，算是已经摊开好了
        else if(righte && !lefte)
        {
        }
        //两边都有或者只有左边的情况下，就是把左边的最后一个的下一个接到当前节点的右侧那一路，然后将改节点转移到右侧，最后将左节点清空。返回尾巴，无论是左边还是右边。
        else
        {
            lefte->right = root->right;
            root->right = root->left;

        }
        root->left = nullptr;
        // 返回尾巴，如果有右侧尾巴的话，他就在最后，否则就是左侧尾巴是最后
        return righte?righte:lefte;
    }
};

// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    // base case
    if (root == null) return;

    flatten(root.left);
    flatten(root.right);

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;

    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

// FIXME:为什么在这里使用迭代器的方法会出现很多问题，无法进行实现，正确的写法应该是怎么杨的？
// lvalue来初始化一个node我知道不行，但是为什么会是左值呢。
// class Solution {
// public:
//     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
//         TreeNode* root = helpbuild(nums.begin(),nums.end());
//         return root;
//     }
//     TreeNode* helpbuild(vector){
//         int max= *begin;
//         for(vector<int>::iterator it=begin; it!=end; it++){
//             if(*it>max)
//                 max = *it;
//         }
//         cout<<max<<endl;
//         TreeNode* inner; 
//         inner->val = max;
//         auto next = find(begin,end,max);
//         inner->left = helpbuild(begin,next);
//         inner->right = helpbuild(next+1,end);
//         return inner;

//     }
// };
class Solution{
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return helpbuild(nums,0,nums.size());
    }
    TreeNode* helpbuild(vector<int>& nums, int begin, int end){
        if(nums.empty() || begin==end)
            return nullptr;
        int maxindex = -1, maxval = INT_MIN;
        for(int i=begin;i<end;i++){
            if (nums[i]>=maxval)
            {
                maxindex = i;
                maxval = nums[i];
            }
        }
        // inner的生存周期问题
        TreeNode* inner = new TreeNode(maxval);
        inner->left = helpbuild(nums,begin,maxindex);
        // 下面这里没有+1的画，会导致一个机器严重的问题，但是我不知道为啥，是溢出了把，永远无法到达终点？
        inner->right = helpbuild(nums,maxindex+1,end);
        return inner;
    }
};

// TODO:这题可以讨论一下python的解法，应该会更简单一点。
// FIXME：这题目前这样的结果十分的差，后序看看其他方法的改进，但是这题的解题思路还是很不错
#include <unordered_map> 
#include <string>
class Solution {
public:
    unordered_map<string,int> memo;
    vector<TreeNode*> res;
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        if(!root)
            return {}; // 这个返回值要记得
        traverse(root);
        return res;
    }
    string traverse(TreeNode* root){
        if(!root)
            return "#";
        string left = traverse(root->left);
        string right = traverse(root->right);
        // 得到一个后序遍历的序列，（但是基于这样的序列怎么判断子树一致呢？）
        // FIXME int到string的转换到底怎么做，好疑惑啊。
        char temp = root->val +'0';
        string resstr = left + "," + right+"," + temp;
        // 压入hashmap，通过数值判断重复的root；通过数值判断就知道有没有重复了
        if(memo.count(resstr))
            memo[resstr]++;
        if (memo[resstr]==1)
            res.push_back(root);
        return resstr;
    }
};

class Codec {
public:
    // 实际上该问题还是突出一个三种遍历方式的问题；
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string BTString;
        string SEP = ",";
        string ENDS = "#";
        if(!root){
            BTString.append(ENDS).append(SEP);
            return BTString;
        }
        
        // 前序遍历位置
        // TODO：连续append的表示形式

        BTString.append(to_string(root->val)).append(SEP);
        BTString.append(serialize(root->left)); 
        BTString.append(serialize(root->right)); 
        return BTString;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        // 切分字符串方法 find & substr?
        // 我们在这里需要的是一个先进先出的情况，所以实际上是一个Quene的类别
        // 但是好像实际上for循环也能满足这个问题，但是如果我试图使用递归的话，那我应该还是要用队列
        // 长度不固定的问题
        // FIXME:String的空值的情况
        if(data=="")
            return nullptr;
        // NOTE: 通过循环将布不恒等的数值压入队列
        queue<string> q;
        string Tmpstr;
        for(int i = 0; i<data.length();i++){
            if(data[i]==','){
                q.push(Tmpstr);
                Tmpstr.clear();
            }
            else{
                // FIXME：append就不行但是push_back就可以，为什么？
                Tmpstr.push_back(data[i]);
            }
        }
        return helprebuild(q);
    }
    TreeNode* helprebuild(queue<string>& que);
};
TreeNode* Codec::helprebuild(queue<string>& que)
{
    TreeNode* root;
    // if (que.empty())
    //     return nullptr;
    string str = que.front();
    if(str == "#")
    {
        que.pop();
        return nullptr;
    }
    // FIXME：还没有给这个类别建立一个存储空间
    root = new TreeNode();
    root->val = stoi(str);
    que.pop();
    root->left = helprebuild(que);
    root->right = helprebuild(que);
    return root;
}

public int countNodes(TreeNode root) {
    TreeNode l = root, r = root;
    // 记录左、右子树的高度
    int hl = 0, hr = 0;
    while (l != null) {
        l = l.left;
        hl++;
    }
    while (r != null) {
        r = r.right;
        hr++;
    }
    // 如果左右子树的高度相同，则是一棵满二叉树
    if (hl == hr) {
        return (int)Math.pow(2, hl) - 1;
    }
    // 如果左右高度不同，则按照普通二叉树的逻辑计算
    // 这里两边都是null的情况就会回归1，不需要额外的判断
    return 1 + countNodes(root.left) + countNodes(root.right);
}

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 用来判断是否两个点都存在在以如今的root所在的树中，如果存在的话就返回True
        // 设计的主要原则：
        // 1. 出现在了后面节点的左边和右边的话，就不可能出现在父节点的左边和右边
        // 2. 再叶节点找到相应的两个指，需要从后面遍历起来，先找到两个节点的位置，然后一级一级的并上来。
        if(!root)
            return nullptr;
        if(root == q || root == p)
            return root;

        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);

        if (left && right)
            return root;
        if (!left && !right)
            return nullptr; 
            
        return left?left:right;
    }
    // bool comexit(TreeNode* root, TreeNode* p, TreeNode* q);
};

class NestedIterator {
private:
    int lens;
    int index;
    vector<int> NestIt; // 关键点在于额外辅助数组的构建，但是是否能够预先建立一个比较长的数组
    // FIXME：通过初始化函数，建立一个比较合适的数组长度，从而减少需要额外分配内存的时间代价。
    // Vector的重新初始化方式。

public:
    // TODO:迭代器的表示形式应该怎么写
    // NOTE：这种题目的阅读逻辑应该怎么分析
    NestedIterator(vector<NestedInteger> &nestedList):index(0) {
        helpBuildVec(nestedList);
    }

    void helpBuildVec(vector<NestedInteger> & nestedList){
        for(int i =0;i<nestedList.size();i++)
        {
            if(nestedList[i].isInteger())
                NestIt.push_back(nestedList[i].getInteger()); // 记得要调用取值的函数
            else
                helpBuildVec(nestedList[i].getList());
        }
        lens = NestIt.size();
    }
    
    int next() {
        return NestIt[index++];
    }
    
    bool hasNext() {
        return index < lens; 
    }
};

class NestedIterator {
private:
  stack<NestedInteger> st;
public:
  NestedIterator(vector<NestedInteger> &nestedList) {
    for (auto iter = nestedList.rbegin(); iter != nestedList.rend(); iter++) {
      st.push(*iter);
    }
  }

  int next() {
    auto t = st.top();
    st.pop();
    return t.getInteger();
  }

  bool hasNext() {
    while (!st.empty()) {
      auto cur = st.top();
      if (cur.isInteger()) return true;
      st.pop();
      auto curList = cur.getList();
      for (auto iter = curList.rbegin(); iter != curList.rend(); iter++) {
        st.push(*iter);
      }
    }
    return false;
  }
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root)
            return nullptr;
        if(root->val == val)
            return root;
        if(val > root->val)
            return searchBST(root->right,val);
        if(val < root->val)
            return searchBST(root->left,val);
        return nullptr;
    }
};

class Solution {
private:
    int count = 0;
    int res = INT_MIN;
public:
    int kthSmallest(TreeNode* root, int k) {
        traverr(root,k);
        return res;
    }
    void traverr(TreeNode* root, int k){
        if (!root)
            return;
        traverr(root->left,k);
        count++;
        if(count==k)
            res = root->val;
        traverr(root->right,k);
    }
};

// FIXME:为什么使用NULL的方法会失效。
// LONG的使用情景，
// 试着用迭代的方式去写（中序遍历）
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helpJudge(root,LONG_MAX,LONG_MIN);
    }
    bool helpJudge(TreeNode* root, long int max,long int min){
        if(!root)
            return true;
        // 这个大于等于等于号不能丢掉。
        if(root->val >= max) return false;
        if(root->val <= min) return false;
        // 根据节点往下迭代的情况，更新最小值和最大值，因为右侧的最小值是不断增长的
        // 而左侧的最大值是在不断的变小的。这一点是这个问题最关键的地方
        return helpJudge(root->right,max,root->val) && helpJudge(root->left,root->val,min);
    }
};

boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    // base case
    if (root == null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValidBST(root.left, min, root) 
        && isValidBST(root.right, root, max);
}

TreeNode insertIntoBST(TreeNode root, int val) {
    // 找到空位置插入新节点
    if (root == null) return new TreeNode(val);
    // if (root.val == val)
    //     BST 中一般不会插入已存在元素
    if (root.val < val) 
        root.right = insertIntoBST(root.right, val);
    if (root.val > val) 
        root.left = insertIntoBST(root.left, val);
    return root;
}

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root){
            TreeNode* curr = new TreeNode(val);
            return curr;
        }
        if (val > root->val)
        {
            if (!root->right)
            {
                TreeNode* curr = new TreeNode(val);
                root->right = curr;
                return root;
            }
            insertIntoBST(root->right,val);
        }
        else
        {
            if(!root->left)
            {
                TreeNode* curr = new TreeNode(val);
                root->left = curr;
                return root;
            }
            insertIntoBST(root->left,val);
        }
        return root;
    }
};

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr) return root;//第一种情况：没找到删除的节点，遍历到空节点直接返回
        if(root->val == key)
        {
            //第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点
            //第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
            if(root->left == nullptr) return root->right;
            //第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if(root->right == nullptr) return root->left;
            //第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            //并返回删除节点右孩子为新的根节点
            else{
                TreeNode* cur = root->right;//找右子树最左面的节点
                while(cur->left != NULL)
                {
                    cur = cur->left;
                }
                cur->left = root->left;//把要删除的节点左子树放在cur的左孩子的位置
                TreeNode* tmp = root;  //把root节点保存一下，下面来删除
                root = root->right;    //返回旧root的右孩子作为新root
                delete tmp;            //释放节点内存
                return root;
            }
        }
        if(root->val > key) root->left = deleteNode(root->left, key);
        if(root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

TreeNode deleteNode(TreeNode root, int key) {
    if (root.val == key) {
        // 找到啦，进行删除
    } else if (root.val > key) {
        // 去左子树找
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        // 去右子树找
        root.right = deleteNode(root.right, key);
    }
    return root;
}