Leetcode Review(6)

Posted on | In |

Leetcode 102 Binary Tree Level Order Traversal

Description:

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]
]

Methods:

Use bfs to go through the whole tree, and use a queue to get the node.

Problem is: how to know the tree level.

We can use a variable count to know this. When count ==0, which means we have accomplish a level of the tree. Then the size of queue would be the number of nodes in the next level.

Everytime we pop a node ,we minus count.

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
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        
        if(root==null) return result;
        
        queue.offer(root);
        int count=1;
        List<Integer> list = new ArrayList<>();
        
        while(!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            count--;
            
            list.add(tmp.val);
            
            if(tmp.left!=null){
                queue.offer(tmp.left);
            }
            if(tmp.right!=null){
                queue.offer(tmp.right);
            }  
            
            if(count==0){
                count=queue.size();
                result.add(list);
                list = new ArrayList<>();
            }       
        }
        return result;     
    }
}

Leetcode 538 Conver BST to Greater Tree

Description:

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.

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

Methods:

Go through the tree from the node which has the largest value to the one that has the least value.(The reverse version of in-order traversal).

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if(root==null) return null;
        Stack<TreeNode> stack = new Stack<>();
        int sum=0;
        TreeNode head = root;
        
        
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.right;  
            }
            TreeNode tmp = stack.pop();
            sum+=tmp.val;
            tmp.val=sum;
            root=tmp.left;
        }
        return head;  
    }
}

Description:

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

1
2
3
4
5
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Methods:

Use dfs

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
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        if(m==0) return false;
        int n = board[0].length;
        
        int k = word.length();
        if(k==0) return false;
        
        boolean[][] visited = new boolean[m][n];
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,m,n,word,i,j,0,visited)) return true;
            }
        }
               
        return false;
    }
    
    private boolean dfs(char[][] board,int m, int n, String word,int i, int j, int index,boolean[][] visited){      
        if(index==word.length()) return true;
        if(i<0||j<0||i>=m||j>=n||visited[i][j]!=false||board[i][j]!=word.charAt(index))
            return false;
        visited[i][j]=true;
        boolean check = dfs(board,m,n,word,i+1,j,index+1,visited)||
                        dfs(board,m,n,word,i-1,j,index+1,visited)||
                        dfs(board,m,n,word,i,j+1,index+1,visited)||
                        dfs(board,m,n,word,i,j-1,index+1,visited);
        visited[i][j]=false;
        return check;
    }
}

Leetcode 212 Word Search II

Description:

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board =

1
2
3
4
5
6
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return 

1
["eat","oath"]

Methods:

Use Word Search

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
36
37
38
39
40
41
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> list = new ArrayList<>();
        int m = board.length;
        if(m==0) return list;
        int n = board[0].length;
        
        int k = words.length;
        if(k==0) return list;
        
        int z=0;
        while(z<k){
            while(z+1<k && words[z]==words[z+1])
                z++;
            boolean[][] visited = new boolean[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(exist(board,words[z],m,n,i,j,0,visited)) 
                        if(!list.contains(words[z]))
                            list.add(words[z]);
                    }
                }
            z++;
            
            }
        return list;
        
    }
    private boolean exist(char[][] board,String word,int m, int n, int i, int j, int index, boolean[][] visited){
        if(index==word.length()) return true;
        if(i<0||j<0||i>=m||j>=n||visited[i][j]||board[i][j]!=word.charAt(index))
            return false;
        visited[i][j]=true;
        boolean check = exist(board,word,m,n,i+1,j,index+1,visited)||
                        exist(board,word,m,n,i-1,j,index+1,visited)||
                        exist(board,word,m,n,i,j+1,index+1,visited)||
                        exist(board,word,m,n,i,j-1,index+1,visited);
        visited[i][j]=false;
        return check;
    }
}

But there is better way..