LeetCode冲刺：Day18

发布于 2022-11-25  40 次阅读

今天按照教程在mint上装Anaconda + Pytorch环境，结果包越装越多，home本身只剩40G左右，装完就剩7G了。当初装双系统时候home分区放在磁盘尾部，不能直接扩容。重装系统太麻烦，就试试拿DiskGenius做无损分区，结果报错。最后是用U盘刻录了一个GParted的LiveCD，启动进去把空闲空间移动到磁盘尾部，再合并给home。

忐忑不安地开机，发现grub没丢，正常进系统了，看着home余量90G，开心。

1. 不同的二叉搜索树 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

由1-n，要返回一个可能的二叉搜索树，可以分解为，确定一个根节点i后，递归左右范围生成可能的左右子树，并从可能的左右子树中选取孩子拼接上来，便形成了一个可能的树，最后得到答案。

代码

class Solution {
private:
    vector<TreeNode*> construct(int start, int end) {
        if (start > end) return {nullptr};
        vector<TreeNode*> allTrees;
        for (int i = start; i <= end; ++i) {
            vector<TreeNode*> leftChild = construct(start, i - 1);
            vector<TreeNode*> rightChild = construct(i + 1, end);

            for (auto& left : leftChild) {
                for (auto& right : rightChild) {
                    TreeNode* root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    allTrees.push_back(root);
                }
            }
        }
        return allTrees;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        return construct(1, n);
    }
};

2. 恢复二叉搜索树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

我只考虑到两个错误节点相聚较远时的情形，而当两个错误节点相邻时，只会有一个地方满足前大于后，这种情况要交换第一个错误节点和他相邻下一个结点的值。

代码

class Solution {
private:
    TreeNode* pre;
    TreeNode* pro1;
    TreeNode* pro2;
    TreeNode* pro12;
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        if (pre && pre->val > root->val) {
            if (!pro1) {
                pro1 = pre;
                pro12 = root;
            }
            else if (!pro2) pro2 = root;
            // pre->val ^= root->val;
            // root->val ^= pre->val;
            // pre->val ^= root->val;
        }
        pre=root;
        inorder(root->right);
    }
public:
    void recoverTree(TreeNode* root) {
        pre = nullptr;
        pro1 = nullptr;
        pro2 = nullptr;
        inorder(root);
        if (pro1 && pro2) {
            pro1->val ^= pro2->val;
            pro2->val ^= pro1->val;
            pro1->val ^= pro2->val;
        } else {
            pro1->val ^= pro12->val;
            pro12->val ^= pro1->val;
            pro1->val ^= pro12->val;
        }
        return;
    }
};

3. 二叉树的锯齿形层序遍历

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

在普通层序遍历的基础上需要实现左右交错的效果，自然想到双端队列。

代码

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        deque<TreeNode*> dq;
        vector<vector<int>> ans;
        dq.push_back(root);
        int seq = 0;
        while (!dq.empty()) {
            int size = dq.size();
            ans.push_back({});
            for (int i = 0; i < size; ++i) {
                if (seq % 2 == 0) {
                    TreeNode* cur = dq.front();
                    dq.pop_front();
                    ans[ans.size()-1].push_back(cur->val);
                    if (cur->left) dq.push_back(cur->left);
                    if (cur->right) dq.push_back(cur->right);
                } else {
                    TreeNode* cur = dq.back();
                    dq.pop_back();
                    ans[ans.size()-1].push_back(cur->val);
                    if (cur->right) dq.push_front(cur->right);
                    if (cur->left) dq.push_front(cur->left);
                }
            }
            seq++;
        }
        return ans;
    }
};

4. 从前序与中序遍历序列构造二叉树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

与后序中序建树的思路类似，分割两个数组来递归建立子树。

代码

class Solution {
private:
    TreeNode* construct(vector<int>& preorder, vector<int>& inoreder) {
        if (inoreder.size() == 0) return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);

        int i = 0;
        for (; i < inoreder.size(); ++i) {
            if (inoreder[i] == root->val) break;
        }

        vector<int> leftIn(inoreder.begin(), inoreder.begin() + i);
        vector<int> rightIn(inoreder.begin() + i + 1, inoreder.end());

        vector<int> leftPre(preorder.begin() + 1, preorder.begin() + leftIn.size() + 1);
        vector<int> rightPre(preorder.begin() + leftIn.size() + 1, preorder.end());

        root->left = construct(leftPre, leftIn);
        root->right = construct(rightPre, rightIn);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return construct(preorder, inorder);
    }
};

5. 路径总和 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

枚举所有路径，路径中可能有负值，所以当前值大于目标值时，不能直接返回。

代码

class Solution {
private:
    vector<vector<int>> ans;
    void backtracking(TreeNode* root, int target, vector<int> path, int sum) {
        path.push_back(root->val);
        sum += root->val;
        if (!root->left && !root->right) {
            if (sum == target) ans.push_back(path);
            return;
        }
        // if (sum >= target) return;

        if (root->left) backtracking(root->left, target, path, sum);
        if (root->right) backtracking(root->right, target, path, sum);
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        ans.clear();
        if (!root) return ans;
        backtracking(root, targetSum, vector<int>(), 0);
        return ans;
    }
};

6. 二叉树展开为链表

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

放到数组中操作。

代码

class Solution {
private:
    void trans(TreeNode* root, vector<TreeNode*>& tree) {
        if (!root) return;
        tree.push_back(root);
        trans(root->left, tree);
        trans(root->right, tree);
    }
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        vector<TreeNode*> tree;
        trans(root, tree);
        for (int i = 0; i < tree.size() - 1; ++i) {
            tree[i]->left = nullptr;
            tree[i]->right = tree[i + 1];
        }
    }
};

7. 填充每个节点的下一个右侧节点指针

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

利用队列层序遍历，只要当前结点不是该层的最后一个，就将其next指向队列头部结点。

代码

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        queue<Node*> que;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; ++i) {
                Node* cur = que.front();
                que.pop();
                if (i < size - 1) cur->next = que.front();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

8. 填充每个节点的下一个右侧节点指针 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

相比上一题，主要是要求使用常数空间。参考这篇。巧妙之处在于，将每一层作为一个链表，遍历当前层的时候，会自然地串起下一层。 这是基于数据结构特点做的层序遍历。

代码

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        Node* cur = root;
        while (cur) {
            Node* dummy = new Node(0);
            Node* pre = dummy;
            while (cur) {
                if (cur->left) {
                    pre->next = cur->left;
                    pre = pre->next;
                }
                if (cur->right) {
                    pre->next = cur->right;
                    pre = pre->next;
                }
                cur = cur->next;
            }
            cur = dummy->next;
        }
        return root;
    }
};

9. 二叉树中的最大路径和

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

抽象出一个结点贡献值的概念，表示以其为根节点的路径总和的最大值，可递归计算。则局部路径最大和是结点值+左结点贡献值+右结点贡献值。而当前结点贡献值等于结点值+max(左、右贡献值)。由此可以递归计算。

代码

class Solution {
private:
int ans = INT_MIN;
    int maxGain(TreeNode* root) {
        if (!root) return 0;
        int leftGain = max(maxGain(root->left), 0);
        int rightGain = max(maxGain(root->right), 0);
        int priceNewPath = root->val + leftGain + rightGain;
        ans = max(ans, priceNewPath);
        return root->val + max(leftGain, rightGain);
    }
public:
    int maxPathSum(TreeNode* root) {
        ans = INT_MIN;
        maxGain(root);
        return ans;
    }
};