LeetCode-10

这个篇章应该二叉树会有挺多的，直接一路打下来。

107 二叉树的层序遍历 II

刷题时间：2021-12-15

直接反转一下？，就这？

 var levelOrderBottom = function(root) {
    const res = [];
    if (!root) return res;
    const que = [];
    que.push(root);
    while (que.length) {
        const length = que.length;
        const arr = [];
        for (let i = 0; i < length; i++) {
            const tmp = que.shift();
            arr.push(tmp.val);
            if (tmp.left) que.push(tmp.left);
            if (tmp.right) que.push(tmp.right);
        }
        res.push(arr);
    }
    return res.reverse();
};

199 二叉树的右视图

刷题时间：2021-12-15

直接按层序遍历走一遍，只不过从右边看一遍

var rightSideView = function (root) {
    const res = [];
    if (!root) return res;
    const que = [];
    que.push(root);
    while (que.length) {
        const length = que.length;
        for (let i = 0; i < length; i++) {
            const tmp = que.shift();
            if (i == 0) res.push(tmp.val);
            if (tmp.right) que.push(tmp.right);
            if (tmp.left) que.push(tmp.left);
        }
    }
    return res;
};

637 二叉树的层平均值

刷题时间：2021-12-15

var averageOfLevels = function (root) {
    const res = [];
    if (!root) return res;
    const que = [];
    que.push(root);
    while (que.length) {
        const length = que.length;
        let sum = 0;
        for (let i = 0; i < length; i++) {
            const tmp = que.shift();
            sum += tmp.val;
            if (tmp.right) que.push(tmp.right);
            if (tmp.left) que.push(tmp.left);
        }
        res.push(sum / length);
    }
    return res;
};

429 N 叉树的层序遍历

刷题时间：2021-12-15

var levelOrder = function (root) {
    const res = [];
    if (!root) return res;
    const que = [];
    que.push(root);
    while (que.length) {
        const length = que.length;
        const arr = [];
        for (let i = 0; i < length; i++) {
            const tmp = que.shift();
            arr.push(tmp.val);
            for (let j = 0; j < tmp.children.length; j++) {
                if (tmp.children[j]) que.push(tmp.children[j]);
            }
        }
        res.push(arr);
    }
    return res;
};

515 在每个树行中找最大值

刷题时间：2021-12-15

var largestValues = function (root) {
    const res = [];
    if (!root) return res;
    const que = [];
    que.push(root);
    while (que.length) {
        const length = que.length;
        let max = -Infinity;
        for (let i = 0; i < length; i++) {
            const tmp = que.shift();
            max = Math.max(tmp.val, max);
            if (tmp.left) que.push(tmp.left);
            if (tmp.right) que.push(tmp.right);
        }
        res.push(max);
    }
    return res;
};

111 二叉树的最小深度

刷题时间：2021-12-15

直接用上一题的题解。

var minDepth = function (root) {
    if (!root) return 0;
    const que = [];
    que.push(root);
    let deep = 0;
    while (que.length) {
        const length = que.length;
        for (let i = 0; i < length; i++) {
            const tmp = que.shift();
            if (!tmp.left && !tmp.right) {
                return deep + 1;
            }
            if (tmp.left) que.push(tmp.left);
            if (tmp.right) que.push(tmp.right);
        }
        deep++;
    }
    return deep;
};

递归法，这个需要处理左边为空或者右边为空，两种不同的情况

var minDepth = function (root) {
    if (!root) return 0;
    const leftDepth = minDepth(root.left);
    const rightDepth = minDepth(root.right);
    if (root.left == null && root.right != null) {
        return 1 + rightDepth;
    }
    if (root.right == null && root.left != null) {
        return 1 + leftDepth;
    }
    return 1 + Math.min(leftDepth, rightDepth);
};

1154 一年中的第几天

刷题时间：2021-12-21

一个星期没刷了，重新开始刷。

关键点就在闰年这一块的，1900就不行，因为被100整除的不行，但是可以被400整除，就有点蛋疼这个规则。

var dayOfYear = function (date) {
    const months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    const arrDate = date.split('-');
    const year = Number(arrDate[0]);
    const month = Number(arrDate[1]);
    const day = Number(arrDate[2]);
    let res = 0;
    for (let i = 0; i < month - 1; i++) {
        res += months[i];
    }
    res += day;
    if (month > 2 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)) {
        res += 1;
    }
    return res;
};

222 完全二叉树的节点个数

刷题时间：2021-12-21

没有利用完全二叉树的特点，先用层序遍历来一遍

var countNodes = function (root) {
    if (!root) return 0;
    const que = [];
    let res = 0;
    que.push(root);
    while (que.length) {
        let length = que.length;
        for (let i = 0; i < length; i++) {
            let node = que.pop();
            res++;
            if(node.left) que.push(node.left);
            if(node.right) que.push(node.right);
        }
    }
    return res;
};

迭代，也没用完全二叉树的特点

var countNodes = function (root) {
    if (!root) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
};

但这个用上了完全二叉树的特点，说实话，有点龙鸣，我感觉不太行，真不如上面那个

var countNodes = function (root) {
    if (!root) return 0;
    let left = root.left;
    let right = root.right;
    let leftHeight = 0,
        rightHeight = 0;
    while (left) {
        left = left.left;
        leftHeight++;
    }
    while (right) {
        right = right.right;
        rightHeight++;
    }
    if (leftHeight == rightHeight) {
        return Math.pow(2, leftHeight + 1) - 1;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
};

110 平衡二叉树

刷题时间：2021-12-21

太好了，我终于是自己写出来的了，好耶。

var isBalanced = function (root) {
    if (!root) return true;
    maxDepth = (root) => {
        if (!root) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    };
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    if (leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1) return false;
    return isBalanced(root.left) && isBalanced(root.right);
};

257 二叉树的所有路径

刷题时间：2021-12-21

这个层序遍历法非常的方便啊，比递归不知道高到哪里去了。

var binaryTreePaths = function (root) {
    const que = [root];
    const paths = [root.val.toString()];
    const res = [];
    while (que.length) {
        let node = que.shift();
        let path = paths.shift();
        if (node.left === null && node.right === null) {
            res.push(path);
        } else {
            if (node.left) {
                que.push(node.left);
                paths.push(path + '->' + node.left.val.toString());
            }
            if (node.right) {
                que.push(node.right);
                paths.push(path + '->' + node.right.val.toString());
            }
        }
    }
    return res;
};

递归，时间也太拉了，过于拉胯了

var binaryTreePaths = function (root) {
    const res = [];
    const getPath = (node, curPath) => {
        if (!node.left && !node.right) {
            curPath += node.val;
            res.push(curPath);
            return;
        }
        curPath += node.val + '->';
        node.left && getPath(node.left, curPath);
        node.right && getPath(node.right, curPath);
    };
    getPath(root, '');
    return res;
};

686 重复叠加字符串匹配

刷题时间：2021-12-22

不会，抄的，用的kmp，该死，太难了

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
const repeatedStringMatch = (a, b) => {
    const an = a.length,
        bn = b.length;
    const index = strStr(a, b);
    if (index === -1) {
        return -1;
    }
    if (an - index >= bn) {
        return 1;
    }
    return Math.floor((bn + index - an - 1) / an) + 2;
};

var strStr = function (haystack, needle) {
    const n = haystack.length,
        m = needle.length;
    if (m === 0) {
        return 0;
    }

    // 创建pi也就是next数组，默认初始化都为0，里面的值表示第n个，下标从1开始
    const pi = new Array(m).fill(0);

    for (let i = 1, k = 0; i < m; i++) {
        // 往前找，找到匹配的。
        while (k > 0 && needle[i] !== needle[k]) {
            k = pi[k - 1];
        }
        if (needle[i] == needle[k]) {
            k++;
        }
        pi[i] = k;
    }
    for (let i = 0, j = 0; i - j < n; i++) {
        while (j > 0 && haystack[i % n] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i % n] == needle[j]) {
            j++;
        }
        if (j === m) {
            return i - m + 1;
        }
    }
    return -1;
};

100 相同的树

刷题时间：2021-12-22

直接借鉴101题的思路，就是有点小区别，比较的是左边对左边，右边对右边，扎不多。

var isSameTree = function (p, q) {
    if (p == null && q == null) return true;
    else if (p == null || q == null) return false;
    else if (p.val != q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

404 左叶子之和

刷题时间：2021-12-22

非常awesome的解法啊。

var sumOfLeftLeaves = function (root) {
    if (root == null) return 0;
    if (root.left && !root.left.left && !root.left.right) {
        return root.left.val + sumOfLeftLeaves(root.right);
    }
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
};

513 找树左下角的值

刷题时间：2021-12-22

层序遍历这么简单，为什么要用什么递归的方法，绕这么远没什么用。

var findBottomLeftValue = function (root) {
    const que = [root];
    let res = 0;
    while (que.length) {
        let len = que.length;
        for (let i = 0; i < len; i++) {
            const node = que.shift();
            if (i == 0) res = node.val;
            if (node.left) que.push(node.left);
            if (node.right) que.push(node.right);
        }
    }
    return res;
};

递归，前、中、后序遍历我都尝试了一下，发现后序遍历速度最快，其次是中序遍历，因为要先找到最底层嘛，后序是先找遍底层，所以中序最快，没得反驳。

var findBottomLeftValue = function (root) {
    let maxLen = -Infinity;
    let res = 0;
    const traversal = (root, len) => {
        root.left && traversal(root.left, len + 1);
        if (!root.left && !root.right) {
            if (len > maxLen) {
                maxLen = len;
                res = root.val;
            }
        }
        root.right && traversal(root.right, len + 1);
    };
    traversal(root, 0);
    return res;
};

113 路径总和 II

刷题时间：2021-12-23

按照112的路径总和思路，都差不多，记得要回溯就行了。

var pathSum = function (root, targetSum) {
    const res = [];
    const dfs = (root, target, path) => {
        if (!root) return;
        path.push(root.val);
        if (!root.left && !root.right && target == root.val) {
            res.push(path.slice());
        }
        dfs(root.left, target - root.val, path);
        dfs(root.right, target - root.val, path);
        path.pop();
    };
    dfs(root, targetSum, []);
    return res;
};

106 从中序与后序遍历序列构造二叉树

刷题时间：2021-12-23

后序和中序遍历的数组：

• 第一步：如果数组大小为零的话，说明是空节点了。
• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
• 第五步：切割后序数组，切成后序左数组和后序右数组
• 第六步：递归处理左区间和右区间

var buildTree = function (inorder, postorder) {
    const postLen = postorder.length;
    if (postLen == 0) return null;
    // 找到后序遍历的最后一个，即根节点
    const root = new TreeNode(postorder[postLen - 1]);
    // 叶子节点就返回
    if (postorder.length == 1) return root;
    // 在中序遍历里面找到这个根节点的位置，然后分成左右
    const rootInIndex = inorder.indexOf(root.val);
    const leftInArr = inorder.slice(0, rootInIndex);
    const rightInArr = inorder.slice(rootInIndex + 1);
    const leftInArrLen = leftInArr.length;
    // 在后序遍历里面根据上述分好的左右数组大小来分后序遍历的左右数组
    const leftPoArr = postorder.slice(0, leftInArrLen);
    const rightPoArr = postorder.slice(leftInArrLen, postorder.length - 1);
    root.left = buildTree(leftInArr, leftPoArr);
    root.right = buildTree(rightInArr, rightPoArr);
    return root;
};

原理相同，精简的写法

var buildTree = function(inorder, postorder) {
    if (!postorder.length) return null;
    const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
    let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
    const root = new TreeNode(rootVal); // 创建中间节点
    root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点
    root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点
    return root;
};

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

刷题时间：2021-12-23
后序和前序是一个道理，只不过一个是最后一个是根节点，一个是第一个是根节点，其他的基本上一模一样。

var buildTree = function (preorder, inorder) {
    if (!preorder.length) return null;
    const rootVal = preorder.shift(); // 从前序遍历的数组中获取中间节点的值， 即数组最后一个值
    let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
    const root = new TreeNode(rootVal); // 创建中间节点
    root.left = buildTree(preorder.slice(0, rootIndex), inorder.slice(0, rootIndex)); // 创建左节点
    root.right = buildTree(preorder.slice(rootIndex), inorder.slice(rootIndex + 1)); // 创建右节点
    return root;
};

1705 吃苹果的最大数目

刷题时间：2021-12-24

需要用到贪心和优先队列，方法比较麻烦

typedef pair<int, int> pii;

class Solution {
   public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        int res = 0;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        int n = apples.size();
        int i = 0;
        while (i < n) {
            while (!pq.empty() && pq.top().first <= i) {
                pq.pop();
            }
            int rottenDay = i + days[i];
            int count = apples[i];
            if (count > 0) {
                pq.emplace(rottenDay, count);
            }
            if (!pq.empty()) {
                pii curr = pq.top();
                pq.pop();
                curr.second--;
                if (curr.second != 0) {
                    pq.emplace(curr.first, curr.second);
                }
                res++;
            }
            i++;
        }
        while (!pq.empty()) {
            while (!pq.empty() && pq.top().first <= i) {
                pq.pop();
            }
            if (pq.empty()) {
                break;
            }
            pii curr = pq.top();
            pq.pop();
            int num = min(curr.first - i, curr.second);
            res += num;
            i += num;
        }
        return res;
    }
};

654 最大二叉树

刷题时间：2021-12-24

这个说实话，不算中等题吧，算简单题吧，提交过的人也不少

var constructMaximumBinaryTree = function (nums) {
    if (nums.length == 0) return null;
    let arr = getMaxIndex(nums);
    let max = arr[0],
        index = arr[1];
    const root = new TreeNode(max);
    root.left = constructMaximumBinaryTree(nums.slice(0, index));
    root.right = constructMaximumBinaryTree(nums.slice(index + 1));
    return root;
};
const getMaxIndex = (arr) => {
    let max = arr[0];
    //声明了个变量 保存下标值
    let index = 0;
    for (let i = 0; i < arr.length; i++) {
        if (max < arr[i]) {
            max = arr[i];
            index = i;
        }
    }
    return [max, index];
};

这个直接在原数组上弄，节省时间和空间，确实更好，只不过效果不是很明显

var constructMaximumBinaryTree = function (nums) {
    const BuildTree = (arr, left, right) => {
        if (left > right)
            return null;
        let maxValue = -1;
        let maxIndex = -1;
        for (let i = left; i <= right; ++i) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
                maxIndex = i;
            }
        }
        let root = new TreeNode(maxValue);
        root.left = BuildTree(arr, left, maxIndex - 1);
        root.right = BuildTree(arr, maxIndex + 1, right);
        return root;
    }
    let root = BuildTree(nums, 0, nums.length - 1);
    return root;
};

530 二叉搜索树的最小绝对差

刷题时间：2021-12-24

var getMinimumDifference = function (root) {
    let pre = 0;
    let res = Infinity;
    flag = false;
    const dfs = (root) => {
        if (!root) return;
        dfs(root.left);
        if (flag) {
            if (root.val - pre < res) res = root.val - pre;
        } else {
            flag = true;
        }
        pre = root.val;
        dfs(root.right);
    };
    dfs(root);
    return res;
};

501 二叉搜索树中的众数

刷题时间：2021-12-24

非常好，错了四次，第五次才成功。

var findMode = function (root) {
    let pre = null;
    let res = 1;
    let ans = [];
    let max = 1;
    const dfs = (root) => {
        if (!root) return;
        dfs(root.left);
        if (pre!=null) {
            if (root.val == pre) max++;
            else {
                if (max > res) {
                    ans = [pre];
                    res = max;
                } else if (max == res) {
                    ans.push(pre);
                }
                max = 1;
            }
        }
        pre = root.val;
        dfs(root.right);
    };
    dfs(root);
    if (max > res) {
        ans = [];
        ans.push(pre);
        res = max;
    } else if (max == res) {
        ans.push(pre);
    }
    return ans;
};

1609 奇偶树

刷题时间：2021-12-25

这种层序遍历的解法太简单了。

var isEvenOddTree = function (root) {
    const que = [root];
    let flag = 0;
    while (que.length) {
        const len = que.length;
        let pre = que.shift();
        if ((flag == 0 && pre.val % 2 == 0) || (flag == 1 && pre.val % 2 == 1)) return false;
        if (pre.left) que.push(pre.left);
        if (pre.right) que.push(pre.right);
        for (let i = 1; i < len; i++) {
            let node = que.shift();
            if (flag == 0 && (node.val % 2 == 0 || node.val <= pre.val)) return false;

            if (flag == 1 && (node.val % 2 == 1 || node.val >= pre.val)) return false;

            pre = node;
            if (node.left) que.push(node.left);
            if (node.right) que.push(node.right);
        }
        flag ^= 1;
    }
    return true;
};

236 二叉树的最近公共祖先

刷题时间：2021-12-25

半抄袭的

var lowestCommonAncestor = function (root, p, q) {
    if (root == p || root == q || root == null) return root;
    const resLeft = lowestCommonAncestor(root.left,p,q);
    const resRight = lowestCommonAncestor(root.right,p,q);
    if (resLeft && resRight) return root;
    if (resLeft) return resLeft;
    if (resRight) return resRight;
    return null;
};

450 删除二叉搜索树中的节点

刷题时间：2021-12-25

tmd，没写出来，干，最关键的就是左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

然后我这个递归写的也不行，有点拉

var deleteNode = function (root, key) {
    if (root === null) return root;
    // 如果碰上了
    if (root.val === key) {
        // 如果左子节点为空，那么就返回右节点
        if (!root.left) return root.right;
        // 如果右子节点为空，那么就返回右节点
        else if (!root.right) return root.left;
        // 如果右子节点为空，那么就返回右节点
        else {
            let cur = root.right;
            while (cur.left) {
                cur = cur.left;
            }
            cur.left = root.left;
            root = root.right;
            return root;
        }
    }
    if (root.val > key) root.left = deleteNode(root.left, key);
    if (root.val < key) root.right = deleteNode(root.right, key);
    return root;
};