Review

  • 200 Number of islands
  • 110 Balanced binary tree
  • 124 Binary Tree Maximum Path Sum
  • 99 Recover Binary Search Tree
  • 133 Clone Graph
  • 114 Flatten Binary Tree to Linked List
  • 199 Binary Tree Right Side View
  • 301 Remove Invalid Parentheses
  • 337 House Robber III
  • 339 Nested List Weight Sum

200 Number of islands

思路： 求多少个联通块，dfs，bfs，unionfind

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
public void dfs(int x,int y,boolean[][]vis,char[][]grid){
        if(x<0||y<0||x>=grid.length||y>=grid[0].length||vis[x][y]||grid[x][y]=='0')
            return;
        vis[x][y]=true;
        dfs(x+1,y,vis,grid);
        dfs(x-1,y,vis,grid);
        dfs(x,y+1,vis,grid);
        dfs(x,y-1,vis,grid);
    }
    public int numIslands(char[][] grid) {
        if(grid.length==0||grid[0].length==0)
            return 0;
        int m = grid.length,n=grid[0].length;
        int cnt=0;
        boolean [][]vis=new boolean[m][n];
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(grid[i][j]=='1' && !vis[i][j]){
                    cnt++;
                    dfs(i,j,vis,grid);
                }
            }
        }
        return cnt;
    }

110 Balanced binary tree

思路： 树平衡这种题一定要计算高度的。笨点的每个结点都要查左右子树高度。

1
2
3
4
5
6
7
8
9
10
11
12
public int getHeight(TreeNode root){
        if(root==null)
            return 0;
        int l = getHeight(root.left);
        int r = getHeight(root.right);
        if(l==-1||r==-1||Math.abs(l-r)>1)
            return -1;
        return Math.max(l,r)+1;
    }
    public boolean isBalanced(TreeNode root) {
        return getHeight(root)!=-1;
    }

124 Binary Tree Maximum Path Sum

思路： 第一次做的时候一脸懵逼，其实仔细想想，我们需要借助一个dfs函数返回一个值供父节点使用，这个值因该是math.max(cur.val,cur.val+left,cur.val+right),不能有cur.val+left+right,这样就会cross，不能再向上拓展了。全局变量记录这四项的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int dfs(TreeNode root,int []res){
       if(root==null)
           return 0;
       int l=dfs(root.left,res);
       int r = dfs(root.right,res);
       int ans=Math.max(l+root.val,Math.max(r+root.val,root.val));
       res[0]=Math.max(Math.max(ans,res[0]),l+r+root.val);
       return ans;
   }
   public int maxPathSum(TreeNode root) {
       int []res=new int[1];
       res[0]=Integer.MIN_VALUE;
       dfs(root,res);
       return res[0];
   }

99 Recover Binary Search Tree

思路： 中序遍历，然后会发现两次pre.val>root.val,你画画图试试，第一次的异常点事pre，第二个异常点事root。笨一点就可以先把值打印，然后就排序，赋值回去。

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
public TreeNode first=null;
    public TreeNode second=null;
    public TreeNode pre=null;
    public void inorder(TreeNode root){
        if(root==null)
            return;
        inorder(root.left);
        if(pre!=null){
            if(pre.val>root.val){
                if(first==null)
                    first=pre;
                second=root;
            }
        }
        pre=root;
        inorder(root.right);
        //pre=root;
    }
    public void recoverTree(TreeNode root){
        inorder(root);
        if(first!=null && second!=null){
            int tmp = first.val;
            first.val=second.val;
            second.val=tmp;
        }
    }

133 Clone Graph

思路： recursive 的方法太简单，简单说说bfs的way，遍历图，如果map里没有，就创建新的node，否则不创建，但是最后都要关联起来

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
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<UndirectedGraphNode,UndirectedGraphNode>map=new HashMap<>();
        if(node==null)
            return null;
        Queue<UndirectedGraphNode>q=new LinkedList<>();
        q.offer(node);
        map.put(node,new UndirectedGraphNode(node.label));
        while(!q.isEmpty()){
            UndirectedGraphNode top = q.poll();
            for(UndirectedGraphNode ne:top.neighbors){
                if(!map.containsKey(ne)){
                    map.put(ne,new UndirectedGraphNode(ne.label));
                    q.offer(ne);
                }
                map.get(top).neighbors.add(map.get(ne));
            }
        }
        return map.get(node);
    }
    
    
    //recursive way
    
    Map<UndirectedGraphNode,UndirectedGraphNode>map=new HashMap<>();
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node==null)
            return null;
        if(!map.containsKey(node)){
            map.put(node,new UndirectedGraphNode(node.label));
            for(UndirectedGraphNode child:node.neighbors)
                map.get(node).neighbors.add(cloneGraph(child));
        }
        return map.get(node);
    }

114 Flatten Binary Tree to Linked List

思路：后续遍历，仔细揣摩一下，当然，也可以iterative

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
TreeNode pre=null;
    public void flatten(TreeNode root) {
        if(root==null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right=pre;
        root.left=null;
        pre=root;
    }
    
    
    public void flatten(TreeNode root) {
        if(root==null)
            return;
        TreeNode node = root;
        while(node!=null){
            if(node.left!=null){
                TreeNode cur = node.left;
                while(cur.right!=null)
                    cur=cur.right;
                cur.right=node.right;
                node.right=node.left;
                node.left=null;
            }
            node=node.right;
        }
    }

199 Binary Tree Right Side View

思路： 和level order很像, bfs的方法我就懒得写

1
2
3
4
5
6
7
8
9
10
11
12
13
public void dfs(List<Integer>res,TreeNode root,int level){
       if(root==null)
           return;
       if(level>=res.size())
           res.add(root.val);
       dfs(res,root.right,level+1);
       dfs(res,root.left,level+1);
   }
   public List<Integer> rightSideView(TreeNode root) {
       List<Integer>res=new ArrayList<>();
       dfs(res,root,0);
       return res;
   }

301 Remove Invalid Parentheses

思路： bfs，暴力枚举每个删除的位置。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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public boolean isValid(String s){
        char []ss=s.toCharArray();
        int cnt=0;
        for(char c:ss){
            if(c=='(')
                cnt++;
            else if(c==')')
                cnt--;
            if(cnt<0)
                break;
        }
        return cnt==0;
    }
    public List<String> removeInvalidParentheses(String s) {
        List<String>res=new ArrayList<>();
        if(isValid(s)){
            res.add(s);
            return res;
        }
        Queue<String>q=new LinkedList<>();
        q.offer(s);
        Map<String,Boolean>vis=new HashMap<>();
        boolean next=true;
        vis.put(s,true);
        while(next && !q.isEmpty()){
            int size=q.size();
            while(size -- >0){
                String top = q.poll();
                int len =top.length();
                for(int i=0;i<len;++i){
                    if(s.charAt(i)=='('||s.charAt(i)==')'){
                        String sub = top.substring(0,i)+top.substring(i+1);
                        if(!vis.containsKey(sub)){
                            vis.put(sub,true);
                            q.offer(sub);
                            if(isValid(sub)){
                                next=false;
                                res.add(sub);
                            }
                        }
                    }
                }
            }
        }
        return res;
    }

337 House Robber III

思路： dfs 返回一个长度为2的数组，一个代表rob了当前node，一个代表没有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[]dfsRob(TreeNode root){
        if(root==null)
            return new int[]{0,0};
        int []res=new int[2];
        //res[0] rob root; res[1] not rob root;
        int []l = dfsRob(root.left);
        int []r =dfsRob(root.right);
        res[0]=l[1]+r[1]+root.val;
        //好好想想，没选中当前node，不代表最大值一定是选左子节点，右子节点。
        res[1]=Math.max(l[0],l[1])+Math.max(r[0],r[1]);
        return res;
    }
    public int rob(TreeNode root) {
        int []res=dfsRob(root);
        return Math.max(res[0],res[1]);
    }

339 Nested List Weight Sum

思路：普通的level by level 求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void dfs(List<NestedInteger>nestedList,int[]res,int level){
        int n=nestedList.size();
        for(int i=0;i<n;++i){
            if(nestedList.get(i).isInteger()){
                res[0]+=level*nestedList.get(i).getInteger();
            }else{
                dfs(nestedList.get(i).getList(),res,level+1);
            }
        }
    }
    public int depthSum(List<NestedInteger> nestedList) {
        int []res=new int[1];
        dfs(nestedList,res,1);
        return res[0];
    }