Day14 二叉树的最近公共祖先+二叉搜索树与双向链表+二叉搜索

TODO:
1.重做二叉树的最近公共祖先
2.重做二叉搜索树与双向链表
3.二叉搜索树的后序遍历序列，的辅助单调栈方法⭐

剑指 Offer 68 - II. 二叉树的最近公共祖先(简单)

啊啊啊啊，没做出来哭泣

class Solution {
public:
    TreeNode* res = nullptr;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {   
        dfs(root,p,q); 
        return res;
    }
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root == nullptr) return false;
        bool lson = dfs(root->left,p,q);
        bool rson = dfs(root->right,p,q);
        if((lson&&rson)||((lson || rson) && (root->val == p->val) || (root->val == q->val))){
            res = root;
        }
        return lson || rson ||root->val == p->val || root->val == q->val;
    }
};

剑指 Offer 36. 二叉搜索树与双向链表

二叉搜索树构建有序的双向链表就想到了中序遍历，瞥了眼答案确认可以中序遍历，然后就写了四十分钟的样子😭。开始没考虑到局部变量会函数运行完内存就被回收的问题。

class Solution {
private:
    Node* pre ,*cur,*first;
    int flag = 1;
    void dfs(Node* root){
        if(root == nullptr) return ;
        dfs(root->left);
        if(pre == nullptr) {pre = root; if(flag){first = root;flag = 0;}}
        else{
            pre->right = root;
            root->left = pre;
            pre = root;
        }
        cur = root;
        dfs(root->right);
        
    }
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return root;
        pre = nullptr;
        dfs(root);
        Node* head = first;
        first->left = cur;
        cur->right = first;
        return head;
    }
};

更简洁的写法

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return nullptr;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
private:
    Node *pre, *head;
    void dfs(Node* cur) {
        if(cur == nullptr) return;
        dfs(cur->left);
        if(pre != nullptr) pre->right = cur;
        else head = cur;
        cur->left = pre;
        pre = cur;
        dfs(cur->right);
    }
};

剑指 Offer 33. 二叉搜索树的后序遍历序列

不会不会，想了二十来分钟吧。没有思路，总觉得一定有什么规律可循，二叉搜索树与后续遍历。左< 右 >根。那么最后一个数字一定是子树的根？剩下的一部分一定得能够分成两部分？一部分都小于根，一部分都大于根。(时间复杂度 O(N^2)，空间复杂度O(N))
这个思路试了一个小时写出来了还是有一些成就感...有思路为什么还会写一个小时呢？边界处理没想清楚...一半一半得来测试，竟然左边部分直接从0开始了。

image.png

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return part(postorder,0,postorder.size()-1);
    }
    bool part(vector<int>& postorder,int left, int right){
        if(left >= right)return true;
        int key = postorder[right];
        int min = postorder[left];
        int i = left;
        while(i < right && key >= postorder[i]){
            if(postorder[left] < min) return false;
            i++;
        }
        int j = i;
        while(j<right && key < postorder[j]){
            j++;
        }
        if(j != right) return false; 
        return  part(postorder,left,i-1)&&part(postorder,i,j-1);
    }

};

image.png

看了下题解辅助单调栈的方法时间复杂度更低(时间复杂度 O(N)，空间复杂度O(N))。

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int big =   INT_MAX;
         stack<int> stk;
        reverse(postorder.begin(),postorder.end());
        for(auto it : postorder){
            if(it > big) return false;
            while(!stk.empty() && stk.top() > it){
                big = stk.top();
                stk.pop();
            }
            stk.push(it);
        }
        return true;
    }
  
};