美文网首页
Day14 二叉树的最近公共祖先+二叉搜索树与双向链表+二叉搜索

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

作者: 吃掉夏天的怪物 | 来源:发表于2021-06-26 12:06 被阅读0次

    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;
        }
      
    };
    

    相关文章

      网友评论

          本文标题:Day14 二叉树的最近公共祖先+二叉搜索树与双向链表+二叉搜索

          本文链接:https://www.haomeiwen.com/subject/iripyltx.html