Posted Updated LeetCode / Medium2 minutes read (About 294 words)

113. Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

回溯，每次将root的值添加到list中。并计算新的sum值。分别向左右子节点进行递归，然后回溯。
当节点没有左右子节点，且sum等于targetSum则将新建的list添加到结果中。
（注意这一步内也需要进行回溯操作。）

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
44
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ret;
    int target;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ret = new ArrayList<>();
        if(root == null) return ret;
        target = targetSum;
        backTrack(root, 0, new ArrayList<>());
        return ret;
    }
    
    private void backTrack(TreeNode root, int sum, List<Integer> nodes){
        if(root.left == null && root.right == null){
            sum += root.val;
            if(sum == target){
                nodes.add(root.val);
                ret.add(new ArrayList<Integer>(nodes));
                nodes.remove(nodes.size()-1);
            }
            return;
        }
        nodes.add(root.val);
        sum += root.val;
        if(root.left != null) backTrack(root.left, sum, nodes);
        if(root.right != null) backTrack(root.right, sum, nodes);
        nodes.remove(nodes.size()-1);
        sum -= root.val;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 463 words)

103. Binary Tree Zigzag Level Order Traversal

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

BFS搜索，每次遍历挤出整层的节点。
根据真值reverse来判断列表顺序。
当reverse为真，则每次添加元素到列表头。
反之则添加元素到列表尾。

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
44
45
46
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Deque<TreeNode> q = new LinkedList<>();
        q.add(root);
        int size = 1;
        boolean reverse = false;
        
        while(!q.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(reverse){
                    level.add(0, curr.val);
                } 
                else{
                    level.add(curr.val);
                } 
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
                    
            }

            reverse = !reverse;
            ret.add(level);
            size = q.size();
        }
        return ret;
    }
}

双端队列，根据真值reverse来判断是取队头还是取队尾。
每层级需要遍历所有的节点。
注意添加节点时也需要根据reverse来决定加入对头还是队尾。
（从一个层级取出时，加入下一个层级元素需要从队列另一边压入。）
同时左右节点的加入顺序也需要调整。

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
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Deque<TreeNode> dq = new LinkedList<>();
        dq.add(root);
        int size = 1;
        boolean reverse = false;
        
        while(!dq.isEmpty()){
            List<Integer> temp = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                if(reverse){
                    TreeNode curr = dq.removeLast();
                    if(curr.right != null) dq.offerFirst(curr.right);
                    if(curr.left != null) dq.offerFirst(curr.left);
                    temp.add(curr.val);
                } 
                else{
                    TreeNode curr = dq.removeFirst();
                    if(curr.left != null) dq.offerLast(curr.left);
                    if(curr.right != null) dq.offerLast(curr.right);
                    temp.add(curr.val);
                } 
            }

            reverse = !reverse;
            ret.add(temp);
            size = dq.size();
        }
        return ret;
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 237 words)

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

以中序遍历的顺序创建节点（代码实现时先序遍历），每次选择范围的中间值mid为根节点。
根节点的左子节点递归左侧left直到mid-1的位置。
根节点的右子节点递归mid+1直到右侧right的位置。
当left > right时，返回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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length-1);
    }
    
    private TreeNode build(int[] nums, int left, int right){
        if(left > right) return null;
        
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid-1);
        root.right = build(nums, mid+1, right);
        
        return root;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 285 words)

139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

动态规划，创建一个数组dp[]，长度为字符串长度+1，记录是否可以达到。
将dp[0]设置为1，表示可以达到。

从可取长度为1开始，遍历直到可取长度为字符串的长度。
用下一个遍历j将字符串分为两部分。（这里j从i-1下降到0会比从0上升到i-1更快。）
当dp[j]可以到达，且当前的哈希表中有(i-j)组成的字符串时，则dp[i]也可以到达。结束第二层循环。
继续搜索更长的字符串是否可以达到。
最后返回dp中的最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        int n = s.length();
        int[] dp = new int[n+1];
        
        for(String word : wordDict){
            set.add(word);
        }
        dp[0] = 1;
        int temp = 0;
        for(int i = 1; i <= n; i++){
            for(int j = i - 1; j >= 0; j--){
                if(dp[j] == 1 && set.contains(s.substring(j, i))){
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[n] == 1; 
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 312 words)

91. Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:

  • “AAJF” with the grouping (1 1 10 6)
  • “KJF” with the grouping (11 10 6)
    Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

动态规划。转移方程的考虑比较麻烦。
当当前的字符不为0时，该为可以自己组成有效编码，因此dp[i] = dp[i-1]。
然后考虑上一位可以和当前位组成有效编码的情况，如果上一位和当前位的数字小于26，且上一位不等于0，则可以联合编码。
因此dp需要再加上前一位可以组成的编码数，即dp[i] += dp[i-2]。
当i等于1时，由于会越界因此我们手动给dp[i]++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(s.charAt(0) == '0') return 0;
        int[]dp = new int[n];
        dp[0] = 1;

        for(int i = 1 ; i < n; i++){
            if(s.charAt(i) != '0'){
                dp[i] = dp[i-1];
            }
            if(s.charAt(i-1) != '0' && (s.charAt(i-1) - '0') * 10 + (s.charAt(i) - '0') <= 26 ){
                if(i > 1) dp[i] += dp[i-2];
                else dp[i]++;
            }
        }
        return dp[n-1];
    }
}
Follow

Recents

Archives

Links

×