Posted Updated LeetCode / Easya minute read (About 137 words)

119. Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

根据杨辉三角形的规则递归。
每次递归行数-1。
根据上一行的返回值，生成新行的列表，然后返回。
如果生成行数为0则返回{1}。

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 List<Integer> getRow(int rowIndex) {
        if(rowIndex == 0){
            List<Integer> ret = new ArrayList();
            ret.add(1);
            return ret;
        }
        
        List<Integer> arr = getRow(rowIndex - 1);
        List<Integer> ret = new ArrayList();
        
        for(int i = 0; i < arr.size()+1; i++){
            if(i == 0 || i == arr.size()){
                ret.add(1);
            }
            else{
                ret.add(arr.get(i) + arr.get(i-1));
            }
        }
        return ret;
    }
}
Posted Updated LeetCode / Easya minute read (About 197 words)

653. Two Sum IV - Input is a BST

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

DFS搜索，每次递归时检查HashSet中是否有当前节点的值。如没有则将目标值减去当前节点的值加入HashSet。如有则返回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
34
/**
 * 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 {
    HashSet<Integer> set;
    public boolean findTarget(TreeNode root, int k) {
        set = new HashSet();
        return dfs(root,k);
    }
    
    private boolean dfs(TreeNode root, int k){
        if(root == null){
            return false;
        }
        if(set.contains(root.val)){
            return true;
        }
        set.add(k - root.val);

        return dfs(root.left,k) || dfs(root.right,k);
    }
}
Posted Updated LeetCode / Easya minute read (About 221 words)

235. Lowest Common Ancestor of a BST

问题
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).”

DFS搜索，如果当前节点为null，则返回null。
如果当前节点小于p和q的值，则递归其左子节点。
反之递归其右子节点。
如果当前节点在p与q之间，则返回当前节点。
该节点是p与q的Lowest Common Ancestor。

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 binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 243 words)

538. Convert BST to Greater Tree

问题
Given the root of 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 the sum of all keys greater than the original key in BST.

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.
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
/**
 * 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;
 *     }
 * }
 */

DFS搜索，设置一个成员变量记录上一个节点的值。
先递归右侧节点。
设置当前节点的值为自身的值加上temp中的值。
更新temp中的值，再递归左侧节点。


class Solution {
    int temp;
    public TreeNode convertBST(TreeNode root) {
        temp = 0;
        dfs(root);
        return root;
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        } 
        dfs(root.right);
        root.val += temp;
        temp = root.val;
        dfs(root.left);
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 291 words)

669. Trim a Binary Search Tree

问题
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

DFS搜索，每次递归带上搜索的范围值。
如果当前节点小于搜索范围，递归当前节点的右子节点。
反之递归当前节点的左子节点。
如果当前节点在搜索范围中，则其左子节点等于递归后的左子节点，右子节点等于递归后的右子节点。
然后返回当前节点。

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
/**
 * 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 trimBST(TreeNode root, int low, int high) {
        if(root == null){
            return null;
        }
        if(root.val < low){
            return trimBST(root.right, low, high);
        }
        if(root.val > high){
            return trimBST(root.left, low, high);
        }
        
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 163 words)

231. Power of Two

问题
Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

位运算，由于2^n^的二进制为[100…00]，当2^n^-1时，其二进制为[11..11]（少一位）。
两者进行按位与（&）运算，得到[000…00]，与0相等。

1
2
3
4
5
6
7
8
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0){
            return false;
        }
        return (n & (n - 1)) == 0;
    }
}

递归，当（n <= 0）时，返回false。
当n等于1时，返回true。
当（n % 2）有余数时，返回false。
递归（n / 2）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0){
            return false;
        }
        if (n == 1){
            return true;
        }
        if (n%2 != 0){
            return false;
        }
        return isPowerOfTwo(n/2);
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 216 words)

112. Path Sum

问题
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

递归，如果当前节点为null则返回false。
计算并更新当前节点的值。
如果当前节点为叶节点，且当前节点的值等于target，则返回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
/**
 * 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 boolean hasPathSum(TreeNode root, int targetSum) {
        return hasPathSum(root,0,targetSum);
    }
    
    private boolean hasPathSum(TreeNode root, int parentVal, int target){
        if (root == null){return false;}
        root.val = root.val + parentVal;
        if (root.left == null && root.right == null && root.val == target){
            return true;
        }
        return ( hasPathSum(root.left, root.val, target) || hasPathSum(root.right, root.val, target));
    }
}
Posted Updated LeetCode / Easya minute read (About 156 words)

226. Invert Binary Tree

问题
Given the root of a binary tree, invert the tree, and return its root.

翻转二叉树。
交换当前节点的左右子节点。
分别递归其左右子节点。
当当前节点的两个节点均为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
37
38
39
/**
 * 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 invertTree(TreeNode root) {
        if (root == null){
            return root;
        }
        invert(root);
        return root;
    }
    
    private void invert(TreeNode root){
        if ( root.left == null && root.right == null){
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        if ( root.left != null ){
            invert(root.left);
        }
        if ( root.right != null ){
            invert(root.right);
        }
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 224 words)

784. Letter Case Permutation

答案
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

当前字符如果为数字，则直接添加并递归。（将字符隐式转换为整数判断是否为数字，可提升速度。）
当前字符如果为字母，则大小写分别添加到递归。（类似于回溯。）
当字符串长度与搜寻字符串相等时，添加到列表。

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
class Solution {
    List<String> ans;
    String _s;
    public List<String> letterCasePermutation(String s) {
        ans = new ArrayList();
        _s = s;
        
        backTrack(new StringBuilder(),0);
        return ans;
        
    }
    
    private void backTrack(StringBuilder sb, int i){
        if(i == _s.length()){
            ans.add(sb.toString());
            return;
        }
        char curr = _s.charAt(i);
        if ( isNums(curr) ){
            sb.append(curr);
            backTrack(sb, i+1);
        }
        else{
            StringBuilder sb2 = new StringBuilder(sb);
            sb.append(Character.toLowerCase(curr));
            backTrack(sb, i+1);
            sb2.append(Character.toUpperCase(curr));
            backTrack(sb2, i+1);
        }
    }
    
    private boolean isNums(char c){
        if ( (int)c >= (int)'0' && (int)c <= (int)'9' ){
            return true;
        }
        return false;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 181 words)

46. Permutations

问题
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

回溯，建立搜索树。
每次遍历nums中的元素。
如果未遍历过该元素，则向链表及set中添加。
向下递归，链表长度达到nums的长度时返回。
然后从set和链表中移除上一个值，回溯到上一个节点。

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
class Solution {
    List<List<Integer>> ans;
    HashSet<Integer> set;
    public List<List<Integer>> permute(int[] nums) {
        ans = new ArrayList();
        set = new HashSet();
        backTrack(new LinkedList(), nums, nums.length, nums.length);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list,int[] nums, int n, int k){
        if(k == 0){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i = 0; i < n ; i++){
            if(!set.contains(nums[i])){
                list.add(nums[i]);
                set.add(nums[i]);
                backTrack(list, nums , n, k-1);
                set.remove(nums[i]);
                list.removeLast();
            }
        }
    }
}
Posted Updated LeetCode / Easya minute read (About 187 words)

101. Symmetric Tree

问题
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

递归root1的左子节点和root2的右子节点以及root2的左子节点以及root1的右子节点。如两者不相等则返回false。
如果传入的两个数值有一个为null，则两者不相等时返回false。反之返回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 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 boolean isSymmetric(TreeNode root) {
        return isSymmetric(root,root);
    }
    
    public boolean isSymmetric(TreeNode root1, TreeNode root2){
        if ( root1 == null || root2 == null ){
            if(root1 == root2){return true;}
            else{return false;}
        }
        if ( root1.val == root2.val ){
            return isSymmetric(root1.left,root2.right) && isSymmetric(root1.right,root2.left);
        }
        else{
            return false;
        }
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 215 words)

104. Maximum Depth of Binary Tree

问题
Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

递归，每次返回左子节点和右子节点中较大的结果+1。
当节点为null时返回0。

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.
 * 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 int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

BFS搜索，每次倾倒出队列里所有的元素并将level+1。
搜索完毕返回level。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        int level = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for (int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(curr.left!=null){q.offer(curr.left);}
                if(curr.right!=null){q.offer(curr.right);}
            }
            level++;
        }
        return level;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 228 words)

77. Combinations

问题
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

回溯，构建搜索树。
子节点取出的数值应大于父节点中取出的数值。
直到树高度达到k后返回。

返回时，要new一个List，将原有list传入。
否则添加到ans的值只是list的内存地址。
ArrayList换成LinkedList可以优化一些速度，因为可以直接removeLast。（22ms -> 16ms）
i的范围限制在start到n-k+1，后面的限制容易被忽略，可以大幅度减枝，优化速度。（16ms -> 1ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<>();
        backTrack(new LinkedList(),1,n,k);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list, int start, int n, int k){
        if (k == 0){
            ans.add(new ArrayList(list));
            return;
        }

        for (int i = start; i <= n-k+1; i++){
            list.add(i);
            backTrack(list, i+1, n, k-1);
            list.removeLast();
        }
    }
}
Posted Updated LeetCode / Easya minute read (About 126 words)

145. Binary Tree Postorder Traversal

问题
Given the root of a binary tree, return the postorder traversal of its nodes’ values.

后序遍历。
先递归左子节点。
然后递归右子节点。
最后将当前节点加入数组。

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 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<Integer> ans;
    public List<Integer> postorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        traversal(root.left);
        traversal(root.right);
        ans.add(root.val);
        return;
    }
}
Posted Updated LeetCode / Easya minute read (About 126 words)

94. Binary Tree Inorder Traversal

问题
Given the root of a binary tree, return the inorder traversal of its nodes’ values.

中序遍历。
先递归左子节点。
然后将当前节点加入数组。
最后递归右子节点。

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 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<Integer> ans;
    public List<Integer> inorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        traversal(root.left);
        ans.add(root.val);
        traversal(root.right);
        return;
    }
}
Follow

Recents

Archives

Links

×