LeetCode-4

继续窜稀释刷题

237 删除链表中的节点

刷题时间：2021-11-02

这题我是真的没有想到，居然这么简单。

大意了，居然还有优化的空间，要删除原来的空间，尿了。

class Solution {
   public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        ListNode* next = node->next;
        node->next = node->next->next;
        delete (next);
    }
};

141 环形链表

刷题时间：2021-11-02

空间O(n)

class Solution {
   public:
    bool hasCycle(ListNode* head) {
        ListNode* ptr = head;
        unordered_set<ListNode*> set;
        while (ptr != nullptr) {
            if (set.count(ptr)) {
                return true;
            }
            set.insert(ptr);
            ptr = ptr->next;
        }
        return false;
    }
};

进阶，自己想的方法，空间O(1)，而且时间也很快。

class Solution {
   public:
    bool hasCycle(ListNode* head) {
        ListNode* ptr = head;

        while (ptr != nullptr) {
            if (ptr->val == 1000000) {
                return true;
            }
            ptr->val = 1000000;
            ptr = ptr->next;
        }
        return false;
    }
};

官方的O(1)是快慢指针，时间居然和我上面的持平了，空间居然用的还更少，牛牛牛。

快慢指针如果有环的，迟早会追上的。

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

21 合并两个有序链表

一般般的写法，迭代法

class Solution {
   public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* l3 = new ListNode(-1);
        ListNode* res = l3;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val > l2->val) {
                l3->next = l2;
                l2 = l2->next;
            } else {
                l3->next = l1;
                l1 = l1->next;
            }
            l3 = l3->next;
        }
        // if (l1 != nullptr) {
        //     l3->next = l1;
        // }
        // if (l2 != nullptr) {
        //     l3->next = l2;
        // }
        // 或者直接精简成下面这种写法
        l3->next = l1 == nullptr ? l2 : l1;

        return res->next;
    }
};

居然还有递归法，这我是没想到的，我靠，这个还快一点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

203 移除链表元素

简单

class Solution {
   public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* prev = new ListNode(-1);
        prev->next = head;
        ListNode* cur = prev;
        while (cur != nullptr && cur->next != nullptr) {
            if (cur->next->val == val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        return prev->next;
    }
};

为什么老是有递归？？？？舒服了，这次事件相同，内存消耗还大一点。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) {
            return head;
        }
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

js版本

var removeElements = function (head, val) {
    const prev = new ListNode(-1, head);
    let cur = prev;
    while (cur != null && cur.next != null) {
        if (cur.next.val == val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return prev.next;
};

617 合并二叉树

没想到出来，我遇到二叉树就喜欢迭代，但二叉树最简单的方式还是递归，可惜了。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) {
            return t2;
        }
        if (t2 == nullptr) {
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};

广度优先搜索的就不写了，太长太臭了。

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

我直接抄袭以前抄袭的代码，多重抄袭术

class Solution {
	public:
		Node* connect(Node* root) {
			if (!root) return nullptr;
			if(root->left==nullptr&&root->right==nullptr) {
				return root;
			}
			if (root->left)
				root->left->next = root->right;
			if(root->next)
				root->right->next=root->next->left;
			connect(root->left);
			connect(root->right);
			return root;
		}
};

更喜欢迭代法，符合题意

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

js版本迭代，舒服了

var connect = function (root) {
    if (!root) return null;
    const que = [];
    que.push(root);
    while (que.length) {
        const length = que.length;
        let tmp = que.shift();
        if (tmp.left) que.push(tmp.left);
        if (tmp.right) que.push(tmp.right);
        for (let i = 1; i < length; i++) {
            let tmp2 = que.shift();
            tmp.next = tmp2;
            tmp = tmp2;
            if (tmp.left) que.push(tmp.left);
            if (tmp.right) que.push(tmp.right);
        }
    }
    return root;
};

206 反转链表

刷题时间：2021-11-03

就这个方法最简单了，非常的不错。迭代简单

class Solution {
   public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

还有递归的方法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

js版本

var reverseList = function (head) {
    let prev = null;
    let curr = head;
    while (curr) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
};

83 删除排序链表中的重复元素

刷题时间：2021-11-03

简单好吧

class Solution {
   public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }
        ListNode* cur = head;
        while (cur->next) {
            if (cur->next->val == cur->val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

542 01 矩阵

烦死了，难得想用深度优先来写，居然不行，行不通，我真的草了，只能用广度优先。

class Solution {
   private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

   public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<int>> seen(m, vector<int>(n));
        queue<pair<int, int>> q;
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    q.emplace(i, j);
                    seen[i][j] = 1;
                }
            }
        }

        // 广度优先搜索
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.emplace(ni, nj);
                    seen[ni][nj] = 1;
                }
            }
        }

        return dist;
    }
};

还有个动态规划，不看了，这个比较难。

994 腐烂的橘子

艹，没想到情况这么多，利用上一道题的写法。

class Solution {
   private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

   public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        queue<pair<int, int>> q;
        int t1 = 0, t2 = 0, t3 = 0;
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    q.emplace(i, j);
                    t1++;
                } else if (grid[i][j] == 1) {
                    t3++;
                }
            }
        }

        if (t1 == 0) {
            if (t3) {
                return -1;
            }
            return 0;
        }
        int res = 0;
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            t1--;
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
                    grid[ni][nj] == 1) {
                    grid[ni][nj] = 2;
                    q.emplace(ni, nj);
                    t2++;
                }
            }
            if (t1 == 0) {
                res++;
                t1 = t2;
                t2 = 0;
            }
        }
        for (int a = 0; a < m; a++) {
            for (int b = 0; b < n; b++) {
                if (grid[a][b] == 1) {
                    return -1;
                }
            }
        }
        return res - 1;
    }
};

找了一个优化我的算法的，我给忘了queue也能取size了。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        queue<pair<int,int>> rot;
        vector<int> dx = {0,0,-1,1};
        vector<int> dy = {1,-1,0,0};
        int min = 0;
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                if(grid[i][j] == 2){
                    rot.push({i,j});
                }
            }
        }
        while(!rot.empty()){
            int num = rot.size();
            for(int n = 0;n < num;n ++){
                pair<int,int> fir = rot.front();
                rot.pop();
                for(int i = 0;i < 4;i++){
                int tmp_x = fir.first + dx[i];
                int tmp_y = fir.second + dy[i];
                if(tmp_x>=0&&tmp_x<row&&tmp_y>=0&&tmp_y<col&&grid[tmp_x][tmp_y]==1){
                    grid[tmp_x][tmp_y] = 2;
                    rot.push({tmp_x,tmp_y});
                    }
                }
            }
            if(!rot.empty())
            min++;
        }
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                if(grid[i][j] == 1){
                    return -1;
                }
            }
        }
        return min;
    }
};

42 接雨水

日，暴力法，一定要记住暴力法先。最耻辱的事情就是连暴力法都不会。可惜超时了，过不了。

class Solution {
   public:
    int trap(vector<int>& height) {
        int ans = 0;
        int size = height.size();
        for (int i = 1; i < size - 1; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i; j >= 0; j--) {
                max_left = max(max_left, height[j]);
            }
            for (int j = i; j < size; j++) {
                max_right = max(max_right, height[j]);
            }
            ans += min(max_left, max_right) - height[i];
        }
        return ans;
    }
};

动态规划法，这个挺好理解，先遍历一遍，存储每个点左边和右边。这个方法也一定要记住！！

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

双指针 妙蛙种子都没这么妙好吧

如果左边比右边小，那么说明只能会被左边所限制，那么就去找左边的最大值。

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};

407 接雨水 II

https://www.cnblogs.com/grandyang/p/5928987.html

大概能看得懂，但是我自己写肯定写不出来，优先队列就不会。

class Solution {
   public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty()) return 0;
        int m = heightMap.size(), n = heightMap[0].size(), res = 0,
            mx = INT_MIN;
        // 最小堆
        priority_queue<pair<int, int>, vector<pair<int, int>>,
                       greater<pair<int, int>>> q;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<int>> dir{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    q.push({heightMap[i][j], i * n + j});
                    visited[i][j] = true;
                }
            }
        }
        while (!q.empty()) {
            auto t = q.top();
            q.pop();
            int h = t.first, r = t.second / n, c = t.second % n;
            // 最低的海平面
            mx = max(mx, h);
            for (int i = 0; i < dir.size(); ++i) {
                int x = r + dir[i][0], y = c + dir[i][1];
                if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y])
                    continue;
                visited[x][y] = true;
                if (heightMap[x][y] < mx) res += mx - heightMap[x][y];
                q.push({heightMap[x][y], x * n + y});
            }
        }
        return res;
    }
};

367 有效的完全平方数

刷题时间：2021-11-04

最朴实无法的做法

class Solution {
   public:
    bool isPerfectSquare(int num) {
        int n = sqrt(num);
        return n * n == num;
    }
};

暴力法和二分法不说了。还有个牛顿迭代法

class Solution {
public:
    bool isPerfectSquare(int num) {
        double x0 = num;
        while (true) {
            double x1 = (x0 + num / x0) / 2;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;
    }
};

20 有效的括号

一次性过，空间和时间都拉满。

class Solution {
   public:
    bool isValid(string s) {
        stack<char> sta;
        for (char ch : s) {
            if (ch == '(' || ch == '[' || ch == '{') {
                sta.push(ch);
            } else {
                if (sta.empty()) {
                    return false;
                } else {
                    char tmp = sta.top();
                    switch (ch) {
                        case ')':
                            if (tmp == '(') {
                                sta.pop();
                            } else {
                                return false;
                            }
                            break;
                        case ']':
                            if (tmp == '[') {
                                sta.pop();
                            } else {
                                return false;
                            }
                            break;
                        case '}':
                            if (tmp == '{') {
                                sta.pop();
                            } else {
                                return false;
                            }
                            break;
                        default:
                            break;
                    }
                }
            }
        }
        if (sta.empty()) {
            return true;
        }
        return false;
    }
};

js版本，小技巧，如果左括号匹配，那么就添加右括号，这样子就不用再去匹配了，牛逼方法。

var isValid = function (s) {
    let st = [];
    for (let ch of s) {
        if (ch == '(') st.push(')');
        else if (ch == '[') st.push(']');
        else if (ch == '{') st.push('}');
        else if (st.length == 0 || st[st.length - 1] != ch) return false;
        else st.pop();
    }
    return st.length == 0;
};

232 用栈实现队列

这个均摊的思想很棒啊，每次出摊的时候，才将in的传到out里面，有货的话直接用，没货的话拉一批货。

class MyQueue {
   private:
    stack<int> inStack, outStack;

    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

   public:
    MyQueue() {}

    void push(int x) { inStack.push(x); }

    int pop() {
        if (outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if (outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }

    bool empty() { return inStack.empty() && outStack.empty(); }
};

js版本

var MyQueue = function () {
    this.inStack = [];
    this.outStack = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
    this.inStack.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
    if (this.outStack.length == 0) {
        while (this.inStack.length != 0) {
            this.outStack.push(this.inStack.pop());
        }
    }
    return this.outStack.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    if (this.outStack.length == 0) {
        while (this.inStack.length != 0) {
            this.outStack.push(this.inStack.pop());
        }
    }
    return this.outStack[this.outStack.length - 1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    return this.inStack.length == 0 && this.outStack.length == 0;
};

1218 最长定差子序列

刷题时间：2021-11-05

动态规划，算是比较简单的一道动态规划。

class Solution {
   public:
    int longestSubsequence(vector<int> &arr, int difference) {
        int ans = 0;
        int dp[40001]{0};
        for (int num : arr) {
            dp[num + 20000] = dp[num + 20000 - difference] + 1;
            ans = max(ans, dp[num + 20000]);
        }
        return ans;
    }
};

144 二叉树的前序遍历

递归，自己写的，空间有点拉，因为老是返回一个vector

class Solution {
   public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode *root) {
        if (root) {
            res.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return res;
    }
};

还是推崇下面这个递归

class Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

迭代的方法，非自己写的，之后可能要自己写一遍

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (!stk.empty() || node != nullptr) {
            while (node != nullptr) {
                res.emplace_back(node->val);
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            node = node->right;
        }
        return res;
    }
};

Morris遍历

参考：https://zhuanlan.zhihu.com/p/101321696

其实没什么道理，就是硬记

class Solution {
   public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        TreeNode *p1 = root, *p2 = nullptr;
        while (p1) {
            p2 = p1->left;
            if (p2) {
                while (p2->right && p2->right != p1) {
                    p2 = p2->right;
                }
                if (!p2->right) {
                    res.emplace_back(p1->val);
                    p2->right = p1;
                    p1 = p1->left;
                } else {
                    p2->right = nullptr;
                    p1 = p1->right;
                }
            } else {
                res.emplace_back(p1->val);
                p1 = p1->right;
            }
        }
        return res;
    }
};

js递归

var preorderTraversal = function (root) {
    const res = [];
    const dfs = (node) => {
        if (node === null) return;
        res.push(node.val);
        dfs(node.left);
        dfs(node.right);
    };
    dfs(root);
    return res;
};

js迭代，压栈的顺序先右再左，因为左边的先出来。

var preorderTraversal = function (root) {
    const res = [];
    if (root == null) return [];
    const stk = [];
    stk.push(root);
    while (stk.length != 0) {
        let tmp = stk.pop();
        res.push(tmp.val);
        if (tmp.right) stk.push(tmp.right);
        if (tmp.left) stk.push(tmp.left);
    }
    return res;
};

94 二叉树的中序遍历

递归

class Solution {
   public:
    void inorder(TreeNode *root, vector<int> &res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.emplace_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};

迭代

class Solution {
   public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        stack<TreeNode *> stk;

        TreeNode *node = root;
        while (!stk.empty() || node) {
            while (node) {
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top();
            res.emplace_back(node->val);
            stk.pop();
            node = node->right;
        }
        return res;
    }
};

Morris

class Solution {
   public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        TreeNode *p1 = root, *p2 = nullptr;
        while (p1) {
            p2 = p1->left;
            if (p2) {
                while (p2->right && p2->right != p1) {
                    p2 = p2->right;
                }
                if (!p2->right) {
                    p2->right = p1;
                    p1 = p1->left;
                } else {
                    res.emplace_back(p1->val);
                    p2->right = nullptr;
                    p1 = p1->right;
                }
            } else {
                res.emplace_back(p1->val);
                p1 = p1->right;
            }
        }
        return res;
    }
};

js递归

 var inorderTraversal = function(root) {
    const res = [];
    const dfs = (node) => {
        if (node === null) return;
        dfs(node.left);
        res.push(node.val);
        dfs(node.right);
    };
    dfs(root);
    return res;
};

js迭代

var inorderTraversal = function (root) {
    const res = [];
    if (root == null) return [];
    const stk = [];
    while (stk.length != 0 || root) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        let tmp = stk.pop();
        res.push(tmp.val);
        root = tmp.right;
    }
    return res;
};

145 二叉树的后序遍历

递归简单

class Solution {
   public:
    void postorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }
};

后序迭代需要复习，要不然弄不会。

class Solution {
   public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        stack<TreeNode *> stk;
        TreeNode *prev = nullptr;

        TreeNode *node = root;
        while (!stk.empty() || node) {
            while (node) {
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            if (node->right == nullptr || node->right == prev) {
                res.emplace_back(node->val);
                prev = node;
                node = nullptr;
            } else {
                stk.emplace(node);
                node = node->right;
            }
        }
        return res;
    }
};

这个Morris遍历方法硬背一下就行了，后序真的是最麻烦的

class Solution {
   public:
    void addPath(vector<int> &vec, TreeNode *node) {
        int count = 0;
        while (node != nullptr) {
            ++count;
            vec.emplace_back(node->val);
            node = node->right;
        }
        reverse(vec.end() - count, vec.end());
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        TreeNode *p1 = root, *p2 = nullptr;
        while (p1) {
            p2 = p1->left;
            if (p2) {
                while (p2->right && p2->right != p1) {
                    p2 = p2->right;
                }
                if (!p2->right) {
                    p2->right = p1;
                    p1 = p1->left;
                } else {
                    p2->right = nullptr;
                    p1 = p1->right;
                }
            } else {
                p1 = p1->right;
            }
        }
        return res;
    }
};

js递归

var postorderTraversal = function (root) {
    const res = [];
    const dfs = (node) => {
        if (node === null) return;
        dfs(node.left);
        dfs(node.right);
        res.push(node.val);
    };
    dfs(root);
    return res;
};

js迭代，中右左，然后翻转，这种方法有点trick

var postorderTraversal = function (root) {
    const res = [];
    if (root == null) return [];
    const stk = [];
    stk.push(root);
    while (stk.length != 0) {
        let tmp = stk.pop();
        res.push(tmp.val);
        if (tmp.left) stk.push(tmp.left);
        if (tmp.right) stk.push(tmp.right);
    }
    return res.reverse();
};

正常思维的迭代，但还是非常的难以理解

var postorderTraversal = function (root) {
    const res = [];
    if (root == null) return [];
    const stk = [];
    let prev = null;
    while (stk.length != 0 || root) {
        // 1.遍历到最左子节点
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        // 2.遍历最左子节点的右子树(右子树存在 && 未访问过)
        if (root.right && root.right != prev) {
            // 重复压栈以记录当前路径分叉节点
            stk.push(root);
            root = root.right;
        } else {
            // 后序：填充vec在node->left和node->right后面
            // 注意：此时node的左右子树应均已完成访问
            res.push(root.val);
            // 避免重复访问右子树[记录当前节点便于下一步对比]
            prev = root;
            // 避免重复访问左子树[设空节点]
            root = nullptr;
        }
    }
    return res;
};

77 组合

这种题目的解法就是要有恢复和不恢复两种状态。这样子才能枚举完所有的。

class Solution {
   public:
    vector<int> res;
    vector<vector<int>> ans;
    vector<vector<int>> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }
    void dfs(int cur, int n, int k) {
        if (res.size() + n - cur + 1 < k) {
            return;
        }
        if (res.size() == k) {
            ans.emplace_back(res);
            return;
        }
        res.emplace_back(cur);
        dfs(cur + 1, n, k);
        res.pop_back();
        dfs(cur + 1, n, k);
    }
};

字典法

784 字母大小写全排列

自己参考77组合的经验，不用for循环，那么就会有两个dfs来操作，一个变化前，一个变化后。

class Solution {
   public:
    vector<string> letterCasePermutation(string s) {
        vector<string> res;
        dfs(res, 0, s);
        return res;
    }
    void dfs(vector<string> &res, int i, string s) {
        if (i > s.length() - 1) {
            res.emplace_back(s);
            return;
        }
        dfs(res, i + 1, s);
        if (s[i] <= 'z' && s[i] >= 'a') {
            s[i] = s[i] + 'A' - 'a';
        } else if (s[i] <= 'Z' && s[i] >= 'A') {
            s[i] = s[i] - ('A' - 'a');
        } else {
            return;
        }
        dfs(res, i + 1, s);
    }
};

for循环的思想就是有点搞的。反正有点难想

class Solution {
   public:
    vector<string> letterCasePermutation(string s) {
        vector<string> res;
        dfs(res, 0, s);
        return res;
    }
    void dfs(vector<string> &res, int cur, string s) {
         for (int i = cur; i < s.length(); i++) {
            if (s[i] <= 'z' && s[i] >= 'a') {
                dfs(res, i + 1, s);
                s[i] = s[i] + 'A' - 'a';
            } else if (s[i] <= 'Z' && s[i] >= 'A') {
                dfs(res, i + 1, s);
                s[i] = s[i] - ('A' - 'a');
            }
        }
        res.emplace_back(s);
    }
};

迭代的思想，有点像二叉树的BFS的思路，批处理

class Solution {
   public:
    vector<string> letterCasePermutation(string s) {
        deque<string> res;
        res.emplace_back(s);
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) continue;
            for (int j = res.size(); j > 0; --j) {
                auto sub = res.front();
                res.pop_front();
                res.emplace_back(sub);
                sub[i] ^= (1 << 5);
                res.emplace_back(sub);
            }
        }
        return vector<string>(res.begin(), res.end());
    }
};

还有一种是掩码的方法，这里就不臊皮了。

这题的思路可以参考这题 https://leetcode-cn.com/problems/letter-case-permutation/solution/3chong-hui-su-jie-fa-by-fengziluo-oirf/