力扣Day7

5道easy+10道medium+1道hard，链表基本清晰，复习了树(就做题体验而言我感觉我的树的基础要远强于我的链表😄😭)。

(medium)19. 删除链表的倒数第 N 个结点

双指针，取倒数第k个则用p和q两个指针，q先走k步，然后p和q同步走，当q走到最后null的时候，p就是第k个。代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int cnt = 1;
        ListNode* pre = NULL;
        ListNode* start = head;
        ListNode* end = head;
        while(cnt <= n)
        {
            cnt++;
            end = end->next;
        }
        if(end == NULL)
        {
            head = head->next;
            return head;
        }
        while(end!=NULL)
        {
            pre = start;
            start = start->next;
            end = end->next;
        }
        pre->next = start->next;
        return head;
    }
};

(medium)82. 删除排序链表中的重复元素 II

双链表/双指针，双指针的话一个记录起点，一个记录终点；双链表则是把不存在相同的存进去。代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* now = head;
        ListNode* pre = head;
        ListNode* ans = new ListNode;
        ListNode* l2 = ans;
        //cnt = 0 表示没有判定，=1表示和之前的不同，=2表示和之后的不同
        int cnt = 1;
        bool hasstart = 0;
        while(now != NULL)
        {
            if(pre != now && now->val != pre->val)
            {
                cnt++;
                if(cnt == 2)
                {
                    l2->next = new ListNode(pre->val);
                    cnt = 1;
                    l2 = l2->next;
                }
            }
            else if(pre != now && now->val == pre->val)
                cnt = 0;
            pre = now;
            now = now->next;
        }
        if(cnt)
        {
            if(pre!=NULL)
            {
                l2->next = new ListNode(pre->val);
                l2 = l2->next;
            }
        }
        return ans->next;
    }
};

(medium)61. 旋转链表

我的思路是类似反向链表，因为可以发现，向右移动k%num格等价于head向左移动k%num格，所以先反向链表找head+绕成环，然后再反向，把原来反向链表中的head->next->next指向NULL。效率为O(n+k+n)。代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int num = 0;
        ListNode* now = head;
        ListNode* tmp;
        ListNode* end;
        ListNode* pre = NULL;
        while(now != NULL)
        {
            tmp = now->next;
            now->next = pre;
            pre = now;
            now = tmp;
            num++;
        }
        if(!num)
            return NULL;
        if(pre!=NULL)
            head->next = pre;
        k = k % num;
        while(k)
        {
            k--;
            head = head->next;
        }
        now = head->next;
        end = now;
        pre = head;
        //head->next = NULL;
        while(now != head)
        {
            tmp = now->next;
            now->next = pre;
            pre = now;
            now = tmp;
        }
        int cnt = 0;
        now->next = pre;
        end->next = NULL;
        return head;
    }
};

(medium)86. 分隔链表

其实就是把小于的放一个链表，大于等于的放另外一个链表，最后合在一起；或者说双指针，pre记录之前的节点，如果当前大于等于则把当前节点放入新链表中并循环至找到小于的节点，pre指向这个小于的节点，最后循环结束的pre指向新链表的起始节点。具体代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* now = head;
        ListNode* L = new ListNode();
        ListNode* l1 = L;
        ListNode* ans = new ListNode();
        ListNode* l2 = ans;
        while(now != NULL)
        {
            if(now->val >= x)
            {
                l1->next = new ListNode(now->val);
                l1 = l1->next;
            }
            else
            {
                l2->next = new ListNode(now->val);
                l2 = l2->next;
            }
            now = now->next;
        }
        l2->next = L->next;
        return ans->next;
        //return L->next;
    }
};

(medium)146. LRU 缓存

其实用vector更好模拟，但为了熟悉链表还是写了链表。不知道为啥我delete(head)会有问题，删了就没问题。代码如下：

struct node
{
    int val;
    node *next;
    node *pre;
    node() : val(-1), next(nullptr), pre(nullptr) {}
    node(int x) : val(x), next(nullptr), pre(nullptr) {}
};
class LRUCache {
public:
    int maxn = INT_MAX;
    int cnt = 0;
    node* head;
    node* end;
    //vector<int>s;
    unordered_map<int,int> ans;
    unordered_map<int,node*> pos;
    void print(node* start)
    {
        while(start!=NULL)
        {
            printf("%d ",start->val);
            start = start->next;
        }
        putchar('\n');
    }
    LRUCache(int capacity) {
        //printf("start!\n");
        maxn = capacity;
        cnt = 0;
        head = new node();
        end = head;
    }
    void add(int key, int value)
    {
        end->next = new node(key);
        end->next->pre = end;
        end = end->next;
        if(head == NULL || head->val == -1)
            head = end;
        pos[key] = end;
        ans[key] = value + 1;
    }
    void del()
    {
        node* temp = head;
        if(pos[temp->val]==head)
            ans[temp->val] = 0;
        node* temp2 = head->next;
        if(temp2!=NULL)
        {
            temp2->pre = NULL;
            head = temp2;
        }
    }
    void update(int key, int value)
    {
        node* tmp = pos[key];
        add(key, value);
        if(tmp == head)
            del();
        if(tmp->pre!=NULL)
            tmp->pre->next = tmp->next;
        if(tmp != end)
            tmp->next->pre = tmp->pre;
        delete(tmp);
    }
    int get(int key) {
        if(ans[key])
        {
            int value = ans[key] - 1;
            update(key,value);
            return value;
        }
        else
            return -1;
    }
    //因为value最小值是0，为了避免ans[key]=0和不存在key对应的值混淆，所以都加1进行存储，返回值减1
    void put(int key, int value) {
        if(!ans[key])
        {
            if(cnt<maxn)
            {
                cnt++;
                add(key, value);
            }
            else
            {
                del();
                add(key, value);
                //s.push_back(key);
                //int del = s.front();
            }
        }
        else
        {
            update(key,value);
        }
        //print(head);
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

(easy)104. 二叉树的最大深度

很简单的一道递归题。代码如下：

/**
 * 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:
    int depthfind(TreeNode* now)
    {
        if(now == NULL)
            return 0;
        return 1 + max(depthfind(now->left),depthfind(now->right));
    }
    int maxDepth(TreeNode* root) {
        return depthfind(root);
    }
};

(easy)100. 相同的树

也是一道很简单的递归，只不过是两个指针同时递归罢了。代码如下：

/**
 * 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:
    bool check(TreeNode* a, TreeNode* b)
    {
        if(a == NULL && b == NULL)
            return 1;
        else if(a == NULL || b == NULL)
            return 0;
        if(a->val == b->val && check(a->left,b->left) && check(a->right,b->right))
            return 1;
        return 0;
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return check(p,q);
    }
};

(easy)226. 翻转二叉树

这部分其实只要熟悉树，5min内基本都能做出来。也是一道递归，先把左右节点为根的部分翻转了，再反转左右节点。代码如下：

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
            return  NULL;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        l = invertTree(l);
        r = invertTree(r);
        root->left = r;
        root->right = l;
        return root;
    }
};

(easy)101. 对称二叉树

前两道题的综合，先反转l，再判断翻转后的l树和r树是否相同。代码如下：

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
            return  NULL;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        l = invertTree(l);
        r = invertTree(r);
        root->left = r;
        root->right = l;
        return root;
    }
    bool check(TreeNode* p, TreeNode* q)
    {
        if(p == NULL && q == NULL)
            return 1;
        else if(p == NULL || q == NULL)
            return 0;
        if(p->val == q->val && check(p->left,q->left) && check(p->right,q->right))
            return 1;
        return 0;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return 1;
        TreeNode* l = invertTree(root->left);
        TreeNode* r = root->right;
        return check(l,r);
    }
};

(medium)105. 从前序与中序遍历序列构造二叉树

其实思路很简单，一个二叉树分为三大部分：根、左子树、右子树；而先序遍历是根->左->右，中序遍历是左->根->右，我们只需要递归，当先序中的根=中序中的根时，中序中上一个根到当前根位置为当前根的左子树，右边为右子树。代码如下：

/**
 * 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:
    //l1 是前序遍历数组的起始索引。
    //r1 是前序遍历数组的结束索引。
    //l2 是中序遍历数组的起始索引。
    //r2 是中序遍历数组的结束索引。
    TreeNode* build(int l1, int r1, int l2, int r2)
    {
    if (l1 > r1 || l2 > r2) {
        return nullptr;
    }
    // 找到前序遍历数组中的根节点
    int rootVal = pre[l1];
    // 在中序遍历数组中找到根节点的位置
    int rootIndex = a[rootVal];
    // 创建根节点
    TreeNode *root = new TreeNode(rootVal);
    //左树的长度自然为根节点位置-当前左边界
    int leftSize = rootIndex - l2;
    //先左再右
    //l1+leftsize是表示前序遍历这区间内的所有值都是左子树的，下一个左子树的根节点自然在这区间；而中序遍历由于左子树的值肯定在rootIndex的左边，所以r2 = rootIndex-1
    root->left = build(l1 + 1, l1 + leftSize, l2, rootIndex - 1);
    //左子树区间往右才可能有右子树的根节点所以l1=l1+leftsize+1；而中序遍历由于右子树的值肯定在rootIndex的右边，所以l2 = rootIndex+1
    root->right = build(l1 + leftSize + 1, r1, rootIndex + 1, r2);

    return root;
}
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++)
            a[inorder[i]] = i;
        pre.assign(preorder.begin(),preorder.end());
        TreeNode* root = build(0, preorder.size() - 1, 0, inorder.size() - 1);
        return root;
    }
private:
    unordered_map<int,int> a;
    vector<int> pre;
};

(medium)106. 从中序与后序遍历序列构造二叉树

思路其实类似，只不过从前序遍历从左往右找根节点变成了后序遍历从右往左找根节点。代码如下：

/**
 * 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:
    //l1 是中序遍历数组的起始索引。
    //r1 是中序遍历数组的结束索引。
    //l2 是后序遍历数组的起始索引。
    //r2 是后序遍历数组的结束索引。
    TreeNode* build(int l1 , int r1 , int l2 , int r2)
    {
        if(l1 > r1 || l2 > r2)
            return NULL;
        //找到后序遍历中的根节点
        int rootVal = post[r2];
        //找到根节点在中序遍历中的位置
        int rootIndex = a[rootVal];
        //计算右子树的长度(因为中序遍历为左 中 右，所以中到右边边界的长度为右子树的长度)
        int rightSize = r1 - rootIndex + 1;
        TreeNode* root = new TreeNode(rootVal);
        //在中序遍历中，左子树区间为左边界到根节点左边；在后序遍历中，左子树区间为左边界到右边界-右子树长度
        root->left = build(l1 , rootIndex - 1 , l2 , r2 - rightSize);
        //在中序遍历中，右子树区间为根节点右边到右边界；在后序遍历中，右子树区间为右边界-右子树长度到根节点左边
        root->right = build(rootIndex + 1 , r1 , r2 - rightSize + 1 , r2 - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for(int i = 0; i < inorder.size(); i++)
            a[inorder[i]] = i;
        post.assign(postorder.begin(),postorder.end());
        TreeNode* root = build(0 , inorder.size() - 1 , 0 , postorder.size() - 1);
        return root;
    }
private:
    vector<int> post;
    unordered_map<int,int> a;
};

(medium)117. 填充每个节点的下一个右侧节点指针 II

我的思路是上一个深度和当前节点深度相同的点的next指向当前节点。需要一个哈希表，a[dep]指向上一个深度为dep的节点。由于我是先左后右的遍历，所以在当前节点时其左方深度相同的节点肯定被遍历过了。dep最大为二叉树最深的地方，应该为常量级吧(。代码如下：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    void chase(Node* root, int dep)
    {
        if(root == NULL)
            return ;
        if(a[dep] != NULL)
            a[dep]->next = root;
        a[dep] = root;
        chase(root->left, dep + 1);
        chase(root->right, dep + 1);
        return ;
    }
    Node* connect(Node* root) {
        chase(root,0);
        return root;
    }

private:
    unordered_map<int,Node*> a;
};

(medium)114. 二叉树展开为链表

核心就是先序遍历的先当前节点，再指向左子树，再指向右子树；每次把左、右子树指向的l、r存下来，如果l r都为空则表示当前节点为叶节点，直接返回当前节点；如果l非空，则point->right = l,point->left = NULL，展开左子树，并把左子树最后的一个叶节点指向r；如果r非空，则返回处理后的右子树的叶节点。代码如下：

/**
 * 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:
    TreeNode* print(TreeNode* root)
    {
        if(root == NULL)
            return NULL;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        root->left = NULL;
        if(l == NULL && r == NULL)
            return root;
        if(l != NULL)
            root->right = l;
        TreeNode* temp = print(l);
        TreeNode* temp2 = print(r);
        if(temp != NULL)
        {
            temp->right = r;
        }
        if(temp2 != NULL)
        {
            temp = temp2;
        }
        return temp;
    }
    void flatten(TreeNode* root) {
        root = print(root);
    }
};

(easy)112. 路径总和

就是到叶节点的时候才计算sum，每次递归都传递当前sum+now->val。代码如下：

/**
 * 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:
    bool check(TreeNode* root, int sum)
    {
        if(root == NULL)
            return 0;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        int temp = sum + root->val;
        if(l == NULL && r == NULL)
        {
            if(temp == target)
                return 1;
        }
        if(l != NULL)
        {
            if(check(l, temp))
                return 1;
        }
        if(r != NULL)
        {
            if(check(r, temp))
                return 1;
        }
        return 0;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        target = targetSum;
        return check(root, 0);
    }
private:
    int target;
};

(medium)129. 求根节点到叶节点数字之和

和上题几乎是一个道理，只不过每次传递的sum变成了sum*10+now->val。代码如下：

/**
 * 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:
    int getsum(TreeNode* root, int sum)
    {
        if(root == NULL)
            return 0;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        int temp = sum*10 + root->val;
        if(l == NULL && r == NULL)
            return temp;
        int temp1 = 0;
        if(l != NULL)
        {
            temp1 = getsum(l,temp);
        }
        if(r != NULL)
        {
            temp1 += getsum(r,temp);
        }
        return temp1;
    }
    int sumNumbers(TreeNode* root) {
        return getsum(root, 0);
    }
};

(hard)124. 二叉树中的最大路径和

很简单的一道分治，其实针对经过单个点的最大路径和(指需要往上回溯的)只需要比较三种情况：

1.当前
2.左+当前
3.右+当前

而全局最大路径和的比较对象则稍有不同：

1.经过单个点的最大路径和
2.左+右+当前(这个不能存在在单个点最大路径和上是因为那是需要回溯的，也就意味着会经过当前点两次，因而只能在全局最大路径和里面取)

分清楚了就好处理了，代码如下(maxn2表示经过当前点的最大路径和，maxn表示全局最大路径和)

/**
 * 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:
    int getsum(TreeNode* root)
    {
        if(root == NULL)
            return 0;
        int temp = root->val;
        maxn = max(maxn,temp);
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        if(l == NULL && r == NULL)
            return root->val;
        int temp1 = 0;
        int temp2 = 0;
        int maxn2 = temp;
        if(l != NULL)
        {
            temp1 = getsum(l);
            maxn2 = max(maxn2, temp + temp1);
            maxn = max(maxn, temp1);
        }
        if(r != NULL)
        {
            temp2 = getsum(r);
            maxn2 = max(maxn2, temp + temp2);
            maxn = max(maxn, temp2);
        }
        maxn = max(maxn, maxn2);
        maxn = max(maxn, temp + temp1 + temp2);
        
        
        return maxn2;
    }
    int maxPathSum(TreeNode* root) {
        int temp = getsum(root);
        return maxn;
    }
private:
    int maxn = -INT_MAX;
};