21. 合并两个有序链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} list1
  10.  * @param {ListNode} list2
  11.  * @return {ListNode}
  12.  */
  13. var mergeTwoLists = function(list1, list2) {
  14.     if (list1 === null) {
  15.         return list2
  16.     } else if (list2 === null) {
  17.         return list1
  18.     } else if (list1.val < list2.val) {
  19.         var next = list1.next
  20.         list1.next = mergeTwoLists(list2, next)
  21.         return list1
  22.     } else {
  23.          // 为什么这里else if就挂了
  24.         var next = list2.next
  25.         list2.next = mergeTwoLists(list1, next)
  26.         return list2
  27.     }
  28. };

509. 斐波那契数

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var fib = function(n) {
  6.     if (n <= 1) {
  7.         return n
  8.     }
  9.     return fib(n - 1) + fib(n - 2)
  10. };

94. 二叉树的中序遍历

1、dfs

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number[]}
  12.  */
  13.  // 1、dfs很简单
  14.  //2、用迭代
  15. var inorderTraversal = function(root) {
  16.     var res = []
  18.     var dfs = (root) => {
  19.         if (!root) {
  20.             return
  21.         }
  22.         dfs(root.left)
  23.         res.push(root.val)
  24.         dfs(root.right)
  25.     }
  26.     dfs(root)
  27.     return res
  28. };

2、迭代

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number[]}
  12.  */
  13.  // 1、dfs很简单
  14.  //2、用迭代
  15. var inorderTraversal = function(root) {
  16.     var res = []
  17.     var stack = []
  19.     while(stack.length || root) {
  20.         while(root) {
  21.             stack.push(root)
  22.             root = root.left
  23.         }
  24.         // 左中右
  25.         root = stack.pop()
  26.         res.push(root.val)
  27.         root = root.right
  28.     }
  29.     return res
  30. };

429. N叉树的层序遍历

  1. /**
  2.  * // Definition for a Node.
  3.  * function Node(val,children) {
  4.  *    this.val = val;
  5.  *    this.children = children;
  6.  * };
  7.  */
  9. /**
  10.  * @param {Node|null} root
  11.  * @return {number[][]}
  12.  */
  13. var levelOrder = function(root) {
  14.     let q = [root]
  15.     let res = []
  17.     if (!root) {
  18.         return [];
  19.     }
  21.     while(q.length) {
  22.         let len = q.length
  23.         let level = []
  24.         for (let j = 0; j < len; ++j) {
  25.             let tmp = q.shift()
  26.             for (const child of tmp.children) {
  27.                 q.push(child);
  28.             }
  29.             level.push(tmp.val)
  30.         }
  31.         res.push(level)
  32.     }
  33.     return res
  34. };

48. 旋转图像

  1. // 对于矩阵中第 ii 行的第 jj 个元素，在旋转后，它出现在倒数第 ii 列的第 jj 个位置。
  2. var rotate = function(matrix) {
  3.     const n = matrix.length;
  4.     const matrix_new = new Array(n).fill(0).map(() => new Array(n).fill(0));
  5.     for (let i = 0; i < n; i++) {
  6.         for (let j = 0; j < n; j++) {
  7.             matrix_new[j][n - i - 1] = matrix[i][j];
  8.         }
  9.     }
  10.     for (let i = 0; i < n; i++) {
  11.         for (let j = 0; j < n; j++) {
  12.             matrix[i][j] = matrix_new[i][j];
  13.         }
  14.     }
  15. };