0%

leetcode

Posted on In
Symbols count in article: 66k Reading time ≈ 1:01

leetcode刷题汇总

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map=new Map();
    for(let i=0;i<nums.length;i++){
        let num=nums[i];
        if(map.has(target-nums[i])) {
            return [map.get(target-nums[i]),i];
        }else map.set(nums[i],i);
    }
};

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy=new ListNode(0), 
        cur=dummy,
        carry=0;
    while(l1||l2) {
        let val1=l1?l1.val:0,
            val2=l2?l2.val:0;
        let val=val1+val2+carry;
        let node=new ListNode(val%10);
        carry=Math.floor(val/10);
        cur.next=node;
        cur=node;
        if(l1) l1=l1.next;
        if(l2) l2=l2.next;
    }
    if(carry) {
        let node=new ListNode(carry);
        cur.next=node;
        cur=node;
    }
    cur.next=null;
    return dummy.next;
};

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const res=[];
    nums=nums.sort((a,b)=>a-b);
    for(let i=0;i<nums.length-2;i++) {
        if(i>0&&nums[i]===nums[i-1]) continue; //去除重复的
        let start=i+1,
            end=nums.length-1;
        while(start<end) {
            let sum=nums[i]+nums[start]+nums[end];
            if(sum>0) end--;
            else if(sum<0) start++;
            else {
                res.push([nums[i],nums[start],nums[end]]);
                while(nums[start]===nums[start+1]) start++; //关键 这里会出现重复的
                start++
                while(nums[end]===nums[end-1]) end--;
                end--;
            }
        }
    }
    return res;
};

16. 3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

1
2
3
Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    let min=Number.MAX_VALUE;
    nums=nums.sort((a,b)=>a-b);
    for(let i=0,len=nums.length;i<len-2;i++) {
        let start=i+1,
            end=nums.length-1;
        while(start<end) {
            let sum=nums[i]+nums[start]+nums[end];
            if(Math.abs(sum-target)<Math.abs(min-target)) min=sum;
            if(sum<target) start++;
            else end--;
        }
    }
    return min;
};

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

img

Example:

1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    const map={
        '2':"abc",
        '3':"def",
        '4':"ghi",
        '5':"jkl",
        '6':"mno",
        '7':"prqs",
        '8':"tuv",
        '9':"wxyz"
    }
    const res=[];
    backtrack('',digits)
    return res;
    function backtrack(temp,digits) {
        if(!digits){
            if(!temp) return; //digits=""时
            return res.push(temp);
        }
        for(let i=0;i<map[digits[0]].length;i++) {
            backtrack(temp+map[digits[0]][i],digits.slice(1));
        }
    }
};

18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    const res=[];
    nums=nums.sort((a,b)=>a-b);
    for(let i=0;i<nums.length-3;i++) {
        if(i&&nums[i]===nums[i-1]) continue;
        for(let j=i+1;j<nums.length-2;j++) {
            if(j>i+1&&nums[j]===nums[j-1]) continue;
            let l=j+1,
                r=nums.length-1;
            while(l<r) {
                let sum=nums[i]+nums[j]+nums[l]+nums[r];
                if(sum>target) r--;
                else if(sum<target) l++;
                else {
                    res.push([nums[i],nums[j],nums[l],nums[r]]);
                    while(nums[l]===nums[l+1]) l++;
                    l++;
                    while(nums[r]===nums[r-1]) r--;
                    r--;
                }
            }
        }
    }
    return res;
};

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let dummy={val:0,next:head},
        fast=dummy,
        slow=dummy;
    while(n--) {
        fast=fast.next;
    }
    while(fast.next) {
        slow=slow.next;
        fast=fast.next;
    }
    slow.next=slow.next.next;
    return dummy.next;
};

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let dummy=new ListNode(0),
        cur=dummy;
    while(l1&&l2) {
        if(l1.val<l2.val) {
            cur.next=l1;
            l1=l1.next;
        }else {
            cur.next=l2;
            l2=l2.next;
        }
        cur=cur.next;
    }
    cur.next=l1||l2;
    return dummy.next;
};

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

每一个状态的左括号数大于右括号数，一旦小于，肯定是不满足的

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const res=[];
    generate(n,n,'');
    return res;
    function generate(l,r,s) {
        if(l>r) return;
        if(!l&&!r) return res.push(s);
        if(l) generate(l-1,r,s+'(');
        if(r) generate(l,r-1,s+')');
    }
};

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if(lists.length===0) return null;
    if(lists.length===1) return lists[0];
    let mid=Math.floor(lists.length/2)
    let l1=lists.slice(0,mid),
        l2=lists.slice(mid);
    return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
};

function mergeTwoLists(l1,l2) {
    let dummy=new ListNode(0),
        cur=dummy;
    while(l1&&l2) {
        if(l1.val<l2.val) {
            cur.next=l1;
            l1=l1.next;
        }else {
            cur.next=l2;
            l2=l2.next;
        }
        cur=cur.next;
    }
    cur.next=l1||l2;
    return dummy.next;
}

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

1
Given 1->2->3->4, you should return the list as 2->1->4->3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let dummy={val:0,next:head},
        cur=dummy;
    while(cur.next&&cur.next.next) {
        let node1=cur.next,
            node2=cur.next.next;
        node1.next=node2.next;
        node2.next=node1;
        cur.next=node2;
        cur=cur.next.next;
    }
    return dummy.next;
};

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

  • Only constant extra memory is allowed.
  • You may not alter the values in the list’s nodes, only nodes itself may be changed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    if(!head) return null;
    let prev=cur=head;
    for(let i=0;i<k;i++) {
        if(!cur) return head;
        cur=cur.next;
    }
    let newList=reverseK(prev,cur);
    prev.next=reverseKGroup(cur,k); //继续反转后面k个节点
    return newList;
};

function reverseK(a,b) { //翻转[a,b)的链表
    let prev=null,
        cur=a;
    while(cur!==b) {
        let next=cur.next;
        cur.next=prev;
        prev=cur;
        cur=next;
    }
    return prev;
}

39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const res=[];
    backtrack(res,0,[],candidates,target);
    return res;
};

function backtrack(res,temp,tempArr,candidates,target) {
    if(temp===target) return res.push([...tempArr]);
    else if(temp>target) return;
    for(let i=0;i<candidates.length;i++) {
        //和Combination一样，不能出现相同组合的子集，所以要规定选的范围
        if(candidates[i]<tempArr[tempArr.length-1]) continue
        tempArr.push(candidates[i]);
        backtrack(res,temp+candidates[i],tempArr,candidates,target);
        tempArr.pop();
    }
}

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
7
8
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

1
2
3
4
5
6
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    const res=[];
    backtrack(res,0,[],candidates.sort((a,b)=>a-b),target,0);
    return res;
};

function backtrack(res,temp,tempArr,candidates,target,start) {
    if(temp===target) return res.push([...tempArr]);
    else if(temp>target) return;
    for(let i=start;i<candidates.length;i++) {
        if(i>start&&candidates[i]===candidates[i-1]) continue; //同一深度把相同的元素排除掉
        tempArr.push(candidates[i]);
        backtrack(res,temp+candidates[i],tempArr,candidates,target,i+1);
        tempArr.pop();
    }
}

60. Permutation Sequence

The set [1,2,3,...,*n*] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

1
2
Input: n = 3, k = 3
Output: "213"

Example 2:

1
2
Input: n = 4, k = 9
Output: "2314"

思路

如果直接把所有的排列组合算出来再输出第k个组合的话，时间和空间复杂度会很高。

我们可以观察到：

n=3时

  • 123
  • 132
  • 213
  • 231
  • 312
  • 321

发现开头的数字俩俩一组，即(n-1)!所以我们可以对k进行操作，k/(n-1)!是第几组，即确定了前面的数字，k%(n-1)!是下个递归的开始。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
    let arr=Array(n),
        temp=1,
        res='';
    for(let i=0;i<n;i++) {
        arr[i]=i+1;
        temp*=arr[i];
    }
    temp/=n;
    k--;//如果k整除temp的话，会出现边界数组找不到情况，所以统一处理-1
    while(n) {
        let index=Math.floor(k/temp); //第几组
        k%=temp; //下一个循环
        n--;
        temp/=n; //基底
        res+=arr[index];
        arr.splice(index,1); //加入的数字移除
    }
    return res;
};

61. Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

1
2
3
4
5
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    let cur=head,
        len=1;
    if(!head) return head;
    while(cur.next) {
        len++;
        cur=cur.next;
    }
    cur.next=head;
    k=len-k%len;
    cur=head;
    while(--k) {
        cur=cur.next;
    }
    let newNode=cur.next;
    cur.next=null;
    return newNode;
};

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const res=[];
    backtrack(res,[],n,k,1);
    return res;
};

function backtrack(res,tempArr,n,k,start) {
    if(tempArr.length===k) return res.push([...tempArr]);
    for(let i=start;i<=n;i++) {
        if(tempArr.includes(i)) continue; //重复的过滤掉
        tempArr.push(i);
        backtrack(res,tempArr,n,k,i+1); //防止下次选的比前面一个数小
        tempArr.pop();
    }
}

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const res=[];
    backtrack(res,[],nums,0);
    return res;
};

function backtrack(res,tempArr,nums,start) {
    res.push([...tempArr]); //不限制长度 所以这里直接插入
    for(let i=start;i<nums.length;i++) {
        tempArr.push(nums[i]);
        backtrack(res,tempArr,nums,i+1);
        tempArr.pop();
    }
}

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

1
2
Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

1
2
Input: 1->1->1->2->3
Output: 2->3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if(!head) return head;
    let dummy={val:0,next:head},
        cur=dummy;
    while(cur.next&&cur.next.next) {
        if(cur.next.val===cur.next.next.val) {
            let val=cur.next.val;
            while(cur.next&&cur.next.val===val) {
                cur.next=cur.next.next;
            }
        }else {
            cur=cur.next;
        }
    }
    return dummy.next;
};

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

1
2
Input: 1->1->2
Output: 1->2

Example 2:

1
2
Input: 1->1->2->3->3
Output: 1->2->3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if(!head) return head;
    let cur=head,
        nxt=head; 
    while(cur) {
        while(nxt&&nxt.val===cur.val) nxt=nxt.next; //和当前的cur指向的节点比较
        cur.next=nxt; //下一个不相同的节点找到->连接
        cur=nxt; // 移到下一个需要比较的节点
    }
    return head;
};

86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    let l=new ListNode(0), //俩个用来存放小于x和大于等于x的头节点，最后再拼接
        h=new ListNode(0),
        high=h, //这俩个用来标记初始节点，用于返回和拼接
        res=l;
    while(head) {
        if(head.val<x) {
            l.next=head;
            l=l.next;
        }else {
            h.next=head;
            h=h.next;
        }
        head=head.next;
    }
    l.next=high.next; //拼接
    h.next=null; //尾节点为null
    return res.next;
};

90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
  const res=[];
  backtrack(res,[],nums.sort((a,b)=>a-b),0);
  return res;
};

function backtrack(res,tempArr,nums,start) {
    res.push([...tempArr]);
    for(let i=start;i<nums.length;i++) {
        if(i>start&&nums[i]===nums[i-1]) continue;
        tempArr.push(nums[i]);
        backtrack(res,tempArr,nums,i+1);
        tempArr.pop();
    }
}

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

1
2
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
    let prev=new ListNode(0);
    prev.next=head;
    let dummy=prev; //虚拟节点 用于返回结果
    while(--m) { //找到需要翻转节点的前一个
        prev=prev.next;
        n--;
    }
    let len=n-m+1; //需要翻转的节点数
    let n1=prev, 
        n2=prev.next, //n1、n2是用来翻转的临时节点
        n3=prev.next;//prev、n3一个是翻转节点的前一个节点 一个是翻转节点的第一个
    while(--len) {
        let n4=n2.next;
        n2.next=n1;
        n1=n2;
        n2=n4;
    }
    //此时n1是翻转节点的最后一个、n2是翻转节点的最后一个的下一个节点
    prev.next=n1;
    n3.next=n2;//这俩步是拼接
    return dummy.next;
};

93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

1
2
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const res=[];
    backtrack(res,0,[],s);
    return res;
};

function isValid(s) { //如果大于一位数，但是首字符是'0'，也要排除
    if(s.length>3||(s.length===3&&parseInt(s)>255)||(s.length>1&&s[0]==='0')) return false;
    return true;
}

function backtrack(res,count,tempArr,s) {
    if(!s||count===4) {
        if(!s&&count===4){
            let temp='';
            for(let i=0;i<tempArr.length;i++) {
                if(i) temp+='.'+tempArr[i];
                else temp+=tempArr[i];
            }
            return res.push(temp);
        }
        return;
    }
    for(let i=0;i<s.length;i++) {
        if(isValid(s.slice(0,i+1))) {
            tempArr.push(s.slice(0,i+1));
            backtrack(res,count+1,tempArr,s.slice(i+1));
            tempArr.pop();
        }
    }
}

96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const map={};
    return unique(n);
    function unique(n) {
        if(n<=1) return 1;
        if(map[n]) return map[n];
        let res=0;
        for(let i=1;i<=n;i++) {
            res+=unique(i-1)*unique(n-i);
        }
        map[n]=res;
        return res;   
    }
};

100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

1
2
3
4
5
6
7
Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(!p&&!q) return true;
    if(!p||!q) return false;
    if(p.val!==q.val) return false;
    return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
};

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

recursively

你将根节点的左子树和根节点的右子树的翻转比较是否一样，其实就是100. Same Tree。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
  if(!root) return true;
  return isSame(root.left,root.right);
};

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

iteratively

相当于二叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) return true;
    const stack=[root.left,root.right];
    while(stack.length) {
        let node1=stack.pop(),
            node2=stack.pop();
        if(!node1&&!node2) continue;
        if(!node1||!node2||node1.val!==node2.val) return false;
        //可以很好的俩俩比较
        stack.push(node1.left);
        stack.push(node2.right);
        stack.push(node1.right);
        stack.push(node2.left);
    }
    return true;
};

102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return [];
    let res=[],
        queue=[root];
    while(queue.length) {
        let temp=[],
            len=queue.length;
        //保证了这一循环都是处于一层的
        for(let i=0;i<len;i++) {
            temp.push(queue[i].val);
            if(queue[i].left) queue.push(queue[i].left);
            if(queue[i].right) queue.push(queue[i].right);
        }
        res.push(temp);
        queue.splice(0,len);
    }
    return res;
};

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

和上一题不同的是，根据层次不同插入方向也不同

  • push 尾插
  • unshift 头插
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if(!root) return [];
    let res=[],
        queue=[root],
        flag=false;
    while(queue.length){
        let temp=[],
            len=queue.length;
        flag=!flag;
        for(let i=0;i<len;i++){
            if(flag) temp.push(queue[i].val);
            else temp.unshift(queue[i].val)
            if(queue[i].left) queue.push(queue[i].left);
            if(queue[i].right) queue.push(queue[i].right);
        }
        res.push(temp);
        queue.splice(0,len);
    }
    return res;
};

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0;
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
};

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its bottom-up level order traversal as:

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    if(!root) return [];
    let res=[],
        queue=[root];
    while(queue.length){
        let temp=[],
            len=queue.length;
        for(let i=0;i<len;i++){
            temp.push(queue[i].val);
            if(queue[i].left) queue.push(queue[i].left);
            if(queue[i].right) queue.push(queue[i].right);
        }
        res.unshift(temp);
        queue.splice(0,len);
    }
    return res;
};

109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

1
2
3
4
5
6
7
8
9
Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    if(!head) return null;
    if(!head.next) return new TreeNode(head.val);
    let pre=findMid(head),
        mid=pre.next;
    pre.next=null;
    let node=new TreeNode(mid.val);
    let nxt=mid.next;
    node.left=sortedListToBST(head);
    node.right=sortedListToBST(nxt);
    return node;
    
};

function findMid(head) {
    let pre=slow=fast=head;
    while(fast&&fast.next) {
        pre=slow;
        slow=slow.next;
        fast=fast.next.next
    }
    return pre;
}

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

1
2
3
4
5
6
7
      1
     / \
    2   2
   / \
  3   3
 / \
4   4

Return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    let res=true;
    maxDepth(root);
    return res;
    function maxDepth(root) {
        if(!root) return 0;
        let left=maxDepth(root.left),
            right=maxDepth(root.right);
        if(Math.abs(left-right)>1) return res=false;
        return Math.max(left,right)+1;
    }
};

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(!root) return 0;
    let left=minDepth(root.left),
        right=minDepth(root.right);
    //这里和求最大深度不一样。当左右子节点为0时，不能以0为标准，而是比0大的高度中较小的那个
    if(!left||!right) return left+right+1;
    return Math.min(left,right)+1;
};

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(!root) return false;
    if(!root.left&&!root.right) return sum===root.val;
    return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
};

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    const res=[];
    backtrack(res,[],root,sum);
    return res;
};

function backtrack(res,tempArr,root,sum) {
    //注意边界条件的处理
    if(!root) return;
    if(root.val===sum&&!root.left&&!root.right) return res.push([...tempArr,root.val]);
    tempArr.push(root.val);
    backtrack(res,tempArr,root.left,sum-root.val);
    backtrack(res,tempArr,root.right,sum-root.val);
    tempArr.pop();
}

131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

1
2
3
4
5
6
Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
  const res=[];
  backtrack(res,[],s);
  return res;
};

function isPalindrome(s) {
    let i=0,
        j=s.length-1;
    while(i<j) {
        if(s[i]!==s[j]) return false;
        i++;
        j--;
    }
    return true;
}

function backtrack(res,tempArr,s) {
    if(!s) return res.push([...tempArr]);
    for(let i=0;i<s.length;i++) {
        if(isPalindrome(s.slice(0,i+1))){
            tempArr.push(s.slice(0,i+1));
            backtrack(res,tempArr,s.slice(i+1));
            tempArr.pop();
        }
    }
}

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let slow=fast=head;
    while(fast&&fast.next) {
        slow=slow.next;
        fast=fast.next.next;
        if(slow===fast) return true;
    }
    return false;
};

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if(!head||!head.next) return null;
    let slow=fast=cur=head,
        isCycle=false;
    while(fast&&fast.next) {
        slow=slow.next;
        fast=fast.next.next;
        if(slow===fast) {
            isCycle=true;
            break;
        }
    }
    if(!isCycle) return null;
    while(cur!=slow) {
        cur=cur.next;
        slow=slow.next;
    }
    return cur;
};

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

1
2
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
Input: -1->5->3->4->0
Output: -1->0->3->4->5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if(!head||!head.next) return head;
    let slow=fast=pre=head;
    while(fast&&fast.next) {
        pre=slow;
        slow=slow.next;
        fast=fast.next.next;
    }
    pre.next=null;
    return mergeTwo(sortList(head),sortList(slow));
};

function mergeTwo(l1,l2) {
    let dummy=new ListNode(0),
        cur=dummy;
    while(l1&&l2) {
        if(l1.val<l2.val) {
            cur.next=l1;
            l1=l1.next;
        }else {
            cur.next=l2;
            l2=l2.next;
        }
        cur=cur.next;
    }
    cur.next=l1||l2;
    return dummy.next;
}

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

img

begin to intersect at node c1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let l1=headA,
        l2=headB;
    while(l1!==l2) { //走俩遍
        l1=l1?l1.next:headB;
        l2=l2?l2.next:headA;
    }
    return l1;
};

167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

  • Your returned answers (both index1 and index2) are not zero-based.
  • You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

1
2
3
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let start=0,
        end=numbers.length-1;
    while(start<end) {
        let sum=numbers[start]+numbers[end];
        if(sum<target) start++;
        else if(sum>target) end--;
        else return [start+1,end+1];
    }
};

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

1
2
3
4
5
6
7
8
9
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if(!root) return [];
    let res=[],
        queue=[root];
    while(queue.length) {
        let len=queue.length;
        for(let i=0;i<len;i++) {
            if(i===len-1) res.push(queue[i].val); //每一层最右边的数
            if(queue[i].left) queue.push(queue[i].left);
            if(queue[i].right) queue.push(queue[i].right);
        }
        queue.splice(0,len);
    }
    return res;
};

203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

1
2
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    let dummy={val:0,next:head},
        pre=dummy,
        cur=head;
    while(cur) {
        if(cur.val!==val) { //将需要的节点链接起来
            pre.next=cur;
            pre=cur;
            cur=cur.next;
        }else cur=cur.next;
    }
    pre.next=null;
    return dummy.next;
};

216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

  • All numbers will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

1
2
Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2:

1
2
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const res=[];
    backtrack(res,0,[],k,n,1);
    return res;
};

function backtrack(res,temp,tempArr,num,target,start) {
    if(temp>target||tempArr.length>num) return;
    if(temp===target&&tempArr.length===num) return res.push([...tempArr]);
    for(let i=start;i<=9;i++) {
        tempArr.push(i);
        backtrack(res,temp+i,tempArr,num,target,i+1);
        tempArr.pop();
    }
}

226. Invert Binary Tree

Invert a binary tree.

Example:

Input:

1
2
3
4
5
     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

1
2
3
4
5
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return null;
    [root.left,root.right]=[invertTree(root.right),invertTree(root.left)];
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    const queue=[root];
    while(queue.length) {
        let node=queue.shift();
        if(node) {
            [node.left,node.right]=[node.right,node.left];
            queue.push(node.left,node.right);
        }
    }
    return root;
};

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

1
2
3
4
5
6
7
Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

1
2
3
4
5
6
7
8
9
Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    let stack=[],
        now=0;
    while(root||stack.length) {
        while(root) {
            stack.push(root);
            root=root.left;
        }
        let node=stack.pop();
        if(++now===k) return node.val;
        root=node.right;
    }
};

联想到二叉搜索树的性质，root 大于左子树，小于右子树，如果左子树的节点数目等于 K-1，那么 root 就是结果，否则如果左子树节点数目小于 K-1，那么结果必然在右子树，否则就在左子树。 因此在搜索的时候同时返回节点数目，跟 K 做对比，就能得出结果了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    let count=nodeCount(root.left);
    if(count<k-1) return kthSmallest(root.right,k-1-count);
    else if(count>k-1) return kthSmallest(root.left,k);
    else return root.val;
};

function nodeCount(root) {
    if(!root) return 0;
    let l=nodeCount(root.left),
        r=nodeCount(root.right);
    return l+r+1;
}

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

1
2
Input: 1->2
Output: false

Example 2:

1
2
Input: 1->2->2->1
Output: true

另外一种使用栈的方法也可以，但是空间复杂度高，因为要维护一个栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    if(!head||!head.next) return true;
    let slow=fast=head,
        pre=null,
        nxt;
    while(fast&&fast.next) { //前半部分翻转
        fast=fast.next.next;
        nxt=slow.next;
        slow.next=pre;
        pre=slow;
        slow=nxt;
    }
    if(fast) fast=slow.next;
    else fast=slow;
    slow=pre;
    while(slow&&fast) { //开始比较 前半部分和后半部分
        if(slow.val!==fast.val) return false;
        slow=slow.next;
        fast=fast.next;
    }
    return true;
};

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(root.val<p.val&&root.val<q.val) return lowestCommonAncestor(root.right,p,q);
    if(root.val>p.val&&root.val>q.val) return lowestCommonAncestor(root.left,p,q);
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    while((root.val-p.val)*(root.val-q.val)>0) {
        root=root.val>p.val?root.left:root.right;
    }
    return root;
};

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(!root||root===p||root===q) return root; //边界
    let l=lowestCommonAncestor(root.left,p,q),
        r=lowestCommonAncestor(root.right,p,q); //从上往下
    if(!l) return r;
    if(!r) return l; //从下往上
    return root; //l r都找到了说明此时的这个节点就是LCA
};

257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9
10
11
Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    const res=[];
    backtrack(res,[],root)
    return res;
};

function backtrack(res,tempArr,root){
    if(!root) return;
    if(root&&!root.left&&!root.right) res.push(buildPath([...tempArr,root.val]));
    tempArr.push(root.val);
    backtrack(res,tempArr,root.left);
    backtrack(res,tempArr,root.right);
    tempArr.pop();
}

function buildPath(arr) {
    let res='';
    for(let i=0;i<arr.length;i++) {
        res+=arr[i];
        if(i!=arr.length-1) res+='->';
    }
    return res;
}

328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

1
2
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

1
2
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Note:

  • The relative order inside both the even and odd groups should remain as it was in the input.
  • The first node is considered odd, the second node even and so on …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    if(!head) return null;
    let odd=head,
        even=head.next, //保存头节点，为了后续的拼接
        evenCur=even; 
    while(odd&&evenCur&&evenCur.next) {
        odd.next=odd.next.next;
        odd=odd.next;
        evenCur.next=evenCur.next.next;
        evenCur=evenCur.next;
        cur=odd;
    }
    odd.next=even;
    return head;
};

377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
  • DP: when solve the problem return the count
  • DFS : for return all the possible result

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    let dp=Array(target+1).fill(0);
    dp[0]=1;
    for(let i=1;i<dp.length;i++) {
        for(let j=0;j<nums.length;j++) {
            if(i-nums[j]>=0) dp[i]+=dp[i-nums[j]];
        }
    }
    return dp[target];
};

404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

1
2
3
4
5
6
7
    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    if(!root) return 0;
    if(isLeaf(root.left)) return root.left.val+sumOfLeftLeaves(root.right);
    return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
};

function isLeaf(root) {
    if(!root) return false;
    return !root.left&&!root.right;
}

429. N-ary Tree Level Order Traversal

Given an n-ary tree, return the level order traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

img

1
2
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/**
 * @param {Node} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return [];
    const res=[],
          stack=[root];
    while(stack.length) {
        let len=stack.length,
            temp=[];
        for(let i=0;i<len;i++) {
            temp.push(stack[i].val);
            for(let j=0;j<stack[i].children.length;j++) {
                if(stack[i].children[j]) stack.push(stack[i].children[j]);
            }
        }
        res.push(temp);
        stack.splice(0,len);
    }
    return res;
};

437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    if(!root) return 0;
    let res=0;
    res+=pathSum(root.left,sum)+pathSum(root.right,sum)+pathSumStartWith(root,sum);
    return res;
};

function pathSumStartWith(root,sum) {
    if(!root) return 0;
    let res=0;
    if(root.val===sum) res++;
    res+=pathSumStartWith(root.left,sum-root.val)+pathSumStartWith(root.right,sum-root.val);
    return res;
}

445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    const stack1=[],
          stack2=[],
          stack=[];
    let carry=0,
        dummy=new ListNode(0),
        cur=dummy;
    while(l1) {
        stack1.push(l1.val);
        l1=l1.next;
    }
    while(l2) {
        stack2.push(l2.val);
        l2=l2.next;
    }
    while(stack1.length||stack2.length) {
        let val1=stack1.length?stack1.pop():0,
            val2=stack2.length?stack2.pop():0;
        let val=val1+val2+carry;
        stack.push(val%10);
        carry=Math.floor(val/10);
    }
    if(carry) stack.push(carry);
    while(stack.length) {
        let node=new ListNode(stack.pop());
        cur.next=node;
        cur=node;
    }
    cur.next=null;
    return dummy.next;
};

454. 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

1
2
3
4
5
6
7
8
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @param {number[]} D
 * @return {number}
 */
var fourSumCount = function(A, B, C, D) {
    //空间换时间
    let map={},
        res=0;
    for(let i=0;i<A.length;i++) {
        for(let j=0;j<B.length;j++) {
            map[A[i]+B[j]]=(map[A[i]+B[j]]||0)+1;
        }
    }
    for(let i=0;i<C.length;i++) {
        for(let j=0;j<D.length;j++) {
            res+=map[-(C[i]+D[j])]||0;
        }
    }
    return res;
};

501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

1
2
3
4
5
1
 \
  2
 /
2

return [2].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function(root) {
    let maxVal=[],
        maxNum=0,
        pre=null,
        nowNum=0;
    inorder(root);
    return maxVal;
    function inorder(root) {
        if(!root) return;
        inorder(root.left);
        if(pre&&root.val===pre.val) {
            nowNum++;
            pre=root;
            if(nowNum>maxNum) {
                maxNum=nowNum;
                maxVal=[root.val];
            }else if(nowNum===maxNum) {
                maxVal.push(root.val);
            }
        }else if(pre&&root.val!==pre.val) {
            pre=root;
            nowNum=1;
            if(nowNum===maxNum) maxVal.push(root.val);
        }else {
            pre=root;
            nowNum++;
            maxVal=[root.val];
            maxNum=nowNum;
        }
        inorder(root.right);
    }
};

513. Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

1
2
3
4
5
6
7
8
Input:

    2
   / \
  1   3

Output:
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    let queue=[root],
        node;
    while(queue.length) { //层序遍历的时候可以从右向左放 这样最后一个pop出来的就是最后一行最左边的元素
        node=queue.pop();
        if(node.right) queue.unshift(node.right);
        if(node.left) queue.unshift(node.left);
    }
    return node.val;
};

518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

1
2
3
4
5
6
7
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

1
2
3
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

1
2
Input: amount = 10, coins = [10] 
Output: 1

code

1
2


530. Minimum Absolute Difference in BST

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {
    let node=root,
        stack=[],
        prenode=null,
        min=Number.MAX_VALUE;
    while(node||stack.length) {
        while(node) {
            stack.push(node);
            node=node.left;
        }
        let now=stack.pop();
        if(prenode) min=Math.min(Math.abs(now.val-prenode.val),min);
        prenode=now
        node=now.right;
    }
    return min;
};

538. Convert BST to Greater Tree

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

1
2
3
4
5
6
7
8
9
Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {//递归的话 就按照右-根-左累加
    let sum=0,
        cur=root,
        stack=[];
    while(cur||stack.length) {
        while(cur) {
            stack.push(cur);
            cur=cur.right;
        }
        let node=stack.pop();
        node.val+=sum;
        sum=node.val;
        cur=node.left;
    }
    return root;
};

572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

1
2
3
4
5
    3
   / \
  4   5
 / \
1   2

Given tree t:

1
2
3
  4 
 / \
1   2

Return true, because t has the same structure and node values with a subtree of s.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = function(s, t) {
    if(!s) return false;
    return isSubtree(s.left,t)||isSubtree(s.right,t)||isSubtreeWithRoot(s,t);
};

function isSubtreeWithRoot(s,t) {
    if(!s&&!t) return true;
    if(!s||!t) return false;
    if(s.val!=t.val) return false;
    return isSubtreeWithRoot(s.left,t.left)&&isSubtreeWithRoot(s.right,t.right);
}

589. N-ary Tree Preorder Traversal

Given an n-ary tree, return the preorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Follow up:

Recursive solution is trivial, could you do it iteratively?

Example 1:

img

1
2
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function(root) {
    if(!root) return [];
    const res=[],
          stack=[root];
    while(stack.length) {
        let node=stack.pop();
        res.push(node.val);
        for(let i=node.children.length-1;i>=0;i--) {
            if(node.children[i]) stack.push(node.children[i]);
        }
    }
    return res;
};

617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function(t1, t2) {
    if(!t1&&!t2) return null;
    if(!t1||!t2) return t1||t2;
    let root=new TreeNode(t1.val+t2.val);
    root.left=mergeTrees(t1.left,t2.left);
    root.right=mergeTrees(t1.right,t2.right);
    return root;
};

637. Average of Levels in Binary Tree

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function(root) {
    const queue=[root],
          res=[];
    while(queue.length) {
        let len=queue.length,
            sum=0;
        for(let i=0;i<len;i++) {
            sum+=queue[i].val;
            if(queue[i].left) queue.push(queue[i].left)
            if(queue[i].right) queue.push(queue[i].right)
        }
        sum/=len;
        res.push(sum);
        queue.splice(0,len);
    }
    return res;
};

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {boolean}
 */
var findTarget = function(root, k) {
    const res=[];
    inorder(root);
    function inorder(root) {
        if(!root) return;
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    let i=0,
        j=res.length-1;
    while(i<j) { //双指针
        if(res[i]+res[j]>k) j--;
        else if(res[i]+res[j]<k) i++;
        else return true;
    }
    return false;
};

669. Trim a Binary Search Tree

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: 
    1
   / \
  0   2

  L = 1
  R = 2

Output: 
    1
      \
       2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} L
 * @param {number} R
 * @return {TreeNode}
 */
var trimBST = function(root, L, R) {
    if(!root) return null;
    if(root.val<L) return trimBST(root.right,L,R);
    if(root.val>R) return trimBST(root.left,L,R);
    root.left=trimBST(root.left,L,R);
    root.right=trimBST(root.right,L,R);
    return root;
};

671. Second Minimum Node In a Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

1
2
3
4
5
6
7
8
9
Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findSecondMinimumValue = function(root) {
    const values=new Set();
    function getValue(root) {
        if(!root) return;
        values.add(root.val);
        getValue(root.left);
        getValue(root.right);
    }
    getValue(root);
    return values.size>1?[...values].sort()[1]:-1;
};

725. Split Linked List in Parts

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

Example 1:

1
2
3
4
5
6
7
8
Input:
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].

Example 2:

1
2
3
4
5
Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Note:

The length of root will be in the range [0, 1000].

Each value of a node in the input will be an integer in the range [0, 999].

k will be an integer in the range [1, 50].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} root
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function(root, k) {
    let len=0,
        cur=root;
    while(cur) {
        cur=cur.next;
        len++;
    }
    let count1=len%k,
        num1=Math.floor(len/k);
    const res=[];
    for(let i=0;i<k;i++){
        res[i]=null;
    }
    for(let i=0;i<k&&root;i++) {
        res[i]=root;
        let nowSize=num1+(i<count1?1:0);
        for(let j=0;j<nowSize-1;j++) {
            root=root.next;
        }
        let nxt=root.next;
        root.next=null;
        root=nxt;
    }
    return res;
};

1008. Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

1
2
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @return {TreeNode}
 */
var bstFromPreorder = function(preorder) {
    const inorder=preorder.slice().sort((a,b)=>a-b);
    let pLeft=0,
        pRight=preorder.length-1,
        iLeft=0,
        iRight=inorder.length-1;
    return buildTree(pLeft,pRight,iLeft,iRight)
    function buildTree(pLeft,pRight,iLeft,iRight) {
        if(pLeft>pRight||iLeft>iRight) return null;
        let i=iLeft;
        for(;i<=iRight;i++) {
            if(inorder[i]===preorder[pLeft]) break;
        }
        let node=new TreeNode(preorder[pLeft]);
        node.left=buildTree(pLeft+1,pLeft+i-iLeft,iLeft,i-1);
        node.right=buildTree(pLeft+1+i-iLeft,pRight,i+1,iRight);
        return node;
    }
};

1038. Binary Search Tree to Greater Sum Tree

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var bstToGst = function(root) {
    let stack=[],
        cur=root,
        sum=0;
    while(cur||stack.length) {
        while(cur) {
            stack.push(cur);
            cur=cur.right;
        }
        let node=stack.pop();
        node.val+=sum;
        sum=node.val;
        cur=node.left;
    }
    return root;
};
-------------本文结束感谢您的阅读-------------