MrainW's Home

All things come to those who wait!

0%

Posted on In ,
Symbols count in article: 907 Reading time ≈ 1 mins.

Question

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

https://leetcode.com/problems/permutations/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> res = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(res, new ArrayList<>(), nums);
   return res;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
} 
/*
    Time: O(N!),T(n) = n( c1 + T(n-1) )
    Space: O(N)
*/

Complexity:

Time complexity: O(N!)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 922 Reading time ≈ 1 mins.

Question

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

https://leetcode.com/problems/subsets-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(res, new ArrayList<>(), nums, 0);
    return res;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
} 
/*
    Time: O(n * 2^n) 解的个数*每个解的时间复杂度
    Space: O(n) 额外的数组保存中甲结果
*/

Complexity:

Time complexity: O(n*2^n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 787 Reading time ≈ 1 mins.

Question

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

https://leetcode.com/problems/subsets/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    //Arrays.sort(nums); 不重复没必要sort
    backtrack(res, new ArrayList<>(), nums, 0);
    return res;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

Complexity:

Time complexity: O(n*2^n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.2k Reading time ≈ 1 mins.

Question

Given a binary tree

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

  • Solution1 
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
class Solution {
    public Node connect(Node root) {
      Node dummyHead  = new Node(0); // this head will always point to the first element in the current layer we are searching
      Node pre = dummyHead; // this 'pre' will be the "current node" that builds every single layer   
      Node real_root = root; // just for return statement
        
      while(root != null){
          if(root.left != null){
              pre.next = root.left;
              pre = pre.next;
          }
          if(root.right != null){
              pre.next = root.right; 
              pre = pre.next;
          }
          root = root.next; 
          if(root == null){ // reach the end of current layer
              pre = dummyHead; // shift pre back to the beginning, get ready to point to the first element in next layer  
              root = dummyHead.next; ;//root comes down one level below to the first available non null node
              dummyHead.next = null;//reset dummyhead back to default null
          }
      }
        return real_root;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 746 Reading time ≈ 1 mins.

Question

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public Node connect(Node root) {
        dfs(root, null);        
        return root;
    }
    
    private void dfs(Node curr, Node next) {
        if (curr == null) return;
        curr.next = next;
        dfs(curr.left, curr.right);
        dfs(curr.right, curr.next == null ? null : curr.next.left);
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 724 Reading time ≈ 1 mins.

Question

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

https://leetcode.com/problems/check-completeness-of-a-binary-tree/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        boolean end = false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur == null) end = true;
            else{
                if(end) return false;
                queue.add(cur.left);
                queue.add(cur.right);
            }
        }
        return true;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 673 Reading time ≈ 1 mins.

Question

Given the root of a binary tree, flatten the tree into a “linked list”:

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        // linked list only have 1 direction, the first node must be inserted as first
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 844 Reading time ≈ 1 mins.

Question

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

https://leetcode.com/problems/subtree-of-another-tree/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null) return false;
        if (isSame(s, t)) return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val != t.val) return false;
        return isSame(s.left, t.left) && isSame(s.right, t.right);
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 691 Reading time ≈ 1 mins.

Question

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

https://leetcode.com/problems/diameter-of-binary-tree/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }
    
    private int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        max = Math.max(max, left + right);
        return Math.max(left, right) + 1;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 427 Reading time ≈ 1 mins.

Question

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

https://leetcode.com/problems/invert-binary-tree/

Solution

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
        public TreeNode invertTree(TreeNode root) {
        if(null == root){
            return null;
        }
        
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        
        return root;
        }
}

Complexity:

Time complexity: O(n)

Space complexity: O(h)