IVN
0%

DFS

Posted on Edited on In
Symbols count in article: 33k Reading time ≈ 30 mins.

DFS选编

99. Recover Binary Search Tree

法一：O(n) space 显式inorder

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 class LeetCode99 {
    List<TreeNode> nodes;
    List<Integer> vals;
    public void recoverTree(TreeNode root) {
        nodes=new ArrayList<>();
        vals=new ArrayList<>();
        dfs(root);
        int first=0;
        int second=0;
        for (int i = 1; i < vals.size(); i++) {
            if(vals.get(i-1)>vals.get(i)){
                first=i-1;
                int firstVal=vals.get(first);
                while(i+1<vals.size() && vals.get(i+1)<firstVal){	//firstVal换成vals.get(i)则报错！
                    //[-33,321,55,71,146,231,-13]
                    i++;
                }
                second=i;
                nodes.get(first).val=nodes.get(second).val;
                nodes.get(second).val=firstVal;
                break;
            }
        }
    }

    void dfs(TreeNode root){
        if(root==null){
            return;
        }
        dfs(root.left);
        nodes.add(root);
        vals.add(root.val);
        dfs(root.right);
    }
}

法二：O(1) space 隐式inorder

方法一是显式地将中序遍历的值序列保存在一个 nums 数组中，然后再去寻找被错误交换的节点，但我们也可以隐式地在中序遍历的过程就找到被错误交换的节点 x 和 y。

注意：无需辅助boolean，需要一直比较，确定second的位置！！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    TreeNode t1, t2, pre;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
    }
    public void inorder(TreeNode root){
        if (root == null) return ;
        inorder(root.left);
        if (pre != null && pre.val > root.val) {	//只和前一个节点比较即可
            if (t1 == null) t1 = pre;
            t2 = root;
        }
        pre = root;
        inorder(root.right);
    }
}

1382. Balance a Binary Search Tree

  1. Convert the tree to a sorted array using an in-order traversal.

  2. Construct a new balanced tree from the sorted array recursively.

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
public class LeetCode1382 {
    public TreeNode balanceBST(TreeNode root) {
        Deque<TreeNode> stack=new LinkedList<>();
        List<Integer> list=new ArrayList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            //out: left root right
            //in:  right root left
            TreeNode node=stack.pop();
            if(node!=null){
                if(node.right!=null){
                    stack.push(node.right);
                }
                stack.push(node);
                stack.push(null);
                if(node.left!=null){
                    stack.push(node.left);
                }
            }else{
                list.add(stack.pop().val);
            }
        }
        return construct(list,0,list.size()-1);

    }

    TreeNode construct(List<Integer> list, int start, int end){
        if(start>end || start<0 || end>=list.size()){
            return null;
        }
        if(start==end){
            TreeNode node=new TreeNode(list.get(start));
            return node;
        }
        int mid=start+(end-start)/2;
        TreeNode node=new TreeNode(list.get(mid));
        node.left=construct(list,start,mid-1);
        node.right=construct(list,mid+1,end);
        return node;
    }

}

133. Clone Graph

用数组去重：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Node[] clones;
public Node cloneGraph(Node node) {
    if(node==null){
        return null;
    }
    clones=new Node[101];
    return dfs(node);
}

Node dfs(Node node){
    int val=node.val;
    if(clones[val]!=null){
        return clones[val];
    }
    ArrayList<Node> list=new ArrayList<>();
    Node clone=new Node();
    clone.val=val;
    clone.neighbors=list;
    clones[val]=clone;
    for (Node next : node.neighbors) {
        list.add(dfs(next));
    }
    return clone;
}

用哈希表去重：

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 {
    private HashMap <Node, Node> visited = new HashMap <> ();
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
        Node cloneNode = new Node(node.val, new ArrayList());
        // 哈希表存储
        visited.put(node, cloneNode);

        // 遍历该节点的邻居并更新克隆节点的邻居列表
        for (Node neighbor: node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

156. Binary Tree Upside Down

It is guaranteed that every right node has a sibling (a left node with the same parent) and has no children.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode156 {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root==null){
            return null;
        }
        return reverse(root,root.left,root.right);
    }

    TreeNode reverse(TreeNode root, TreeNode left, TreeNode right){
        if(left==null && right==null){
            return root;
        }
        TreeNode newRoot=reverse(left,left.left,left.right);	//需要记录新树的root，即老树的最左下节点
        left.left=right;
        left.right=root;
        root.left=null;
        root.right=null;
        if(right!=null){
            right.left=null;
            right.right=null;
        }
        return newRoot;
    }
}

250. Count Univalue Subtrees

同值子树，但不同的同值子树同的那个值可以不同

即叶子节点 必定 count as 同值子树

1
2
3
4
5
6
【示例一】
      root = [5,1,5,5,5,null,5]是几个同值子树？ 
     是4个（三个叶子节点5,  一个5->5）
【示例二】
      root = [5,1,5,5,6,null,5]是几个同值子树？
     也是4个（两个叶子节点5, 一个叶子节点6， 一个5->5）
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
int count = 0;
boolean is_uni(TreeNode node) {

    //base case - if the node has no children this is a univalue subtree
    if (node.left == null && node.right == null) {

        // found a univalue subtree - increment
        count++;
        return true;   
    }

    boolean is_unival = true;

    // check if all of the node's children are univalue subtrees and if they have the same value
    // also recursively call is_uni for children
    if (node.left != null) {
        is_unival = is_uni(node.left) && is_unival && node.left.val == node.val;
     }

    if (node.right != null) {
        is_unival = is_uni(node.right) && is_unival && node.right.val == node.val;
    }

    // return if a univalue tree exists here and increment if it does
    if (!is_unival) return false;
    count++;
    return true;
}
public int countUnivalSubtrees(TreeNode root) {
    if (root == null) return 0;
    is_uni(root);
    return count;
}
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
public class LeetCode250 {

    int count;
    public int countUnivalSubtrees(TreeNode root) {
        if(root==null){
            return 0;
        }
        count=0;
        dfs(root);
        return count;
    }

    boolean dfs(TreeNode root){
        if(root.left==null && root.right==null){
            count++;
            return true;
        }
        boolean b=true;
        if(root.left!=null){
            b= dfs(root.left) && root.val==root.left.val;
        }
        if(root.right!=null){
            b= dfs(root.right) && root.val==root.right.val && b;
        }
        if(!b){
            return false;
        }
        count++;
        return true;
    }
}

269. Alien Dictionary

难点：

  1. 理解题意
  2. 拓扑排序 将后序遍历的结果进行反转，就是拓扑排序的结果

https://leetcode.cn/problems/alien-dictionary/solution/-by-max-lfsznscofe-zf3j/

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    public String alienOrder(String[] words) {
        Map<Character, List<Character>> graph = new HashMap<>();
        int n = words.length;
        Set<Character> unknown = new HashSet<>();
        for(String word : words){
            for(int i = 0; i < word.length(); i++){
                unknown.add(word.charAt(i));
            }
        }
        // 1. build graph
        for(int i = 0; i < n - 1; i++){
            String w1 = words[i], w2 = words[i + 1];
            int maxLen = Math.max(w1.length(), w2.length());
            for(int j = 0; j < maxLen; j++){
                if(j == w2.length()) return "";//不合法
                if(j == w1.length()) break;
                if(w1.charAt(j) != w2.charAt(j)){
                    char from = w1.charAt(j), to = w2.charAt(j);
                    if(graph.get(from) == null){
                        graph.put(from, new LinkedList<>());
                    }
                    graph.get(from).add(to);
                    break;//找到第一个不同字母，可以判断顺序
                }
            }

        }
        // 2.topological sort
        visited = new boolean[26];
        onPath = new boolean[26];
        path = new StringBuilder();
        for(char ch : graph.keySet()){
            traverse(graph, ch);
        }
        // 3. get final result
        if(hasCycle) return "";//存在环则无法排序出合法的字母顺序
        for(char unk : unknown){
            if(path.indexOf(String.valueOf(unk)) == -1){
                path.append(unk);
            }
        }
        return path.reverse().toString();

    }

    boolean[] visited;//记录结点访问
    boolean[] onPath;//记录路线访问
    boolean hasCycle;//存在环标志
    StringBuilder path;

    void traverse(Map<Character, List<Character>> graph, char ch){
        if(onPath[ch - 'a']) hasCycle = true;//该路径曾经访问过，存在环
        if(hasCycle || visited[ch - 'a']) return; // 存在环或者已访问过该节点 返回
        visited[ch - 'a'] = true;
        onPath[ch - 'a'] = true;
        if(graph.get(ch) != null){
            for(char next : graph.get(ch)){
                traverse(graph, next);
            }
        }
        path.append(ch);
        onPath[ch - 'a'] = false;
    }

}

269. Alien Dictionary

难点：

  1. 理解题意
  2. 拓扑排序 将后序遍历的结果进行反转，就是拓扑排序的结果

https://leetcode.cn/problems/alien-dictionary/solution/-by-max-lfsznscofe-zf3j/

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    public String alienOrder(String[] words) {
        Map<Character, List<Character>> graph = new HashMap<>();
        int n = words.length;
        Set<Character> unknown = new HashSet<>();
        for(String word : words){
            for(int i = 0; i < word.length(); i++){
                unknown.add(word.charAt(i));
            }
        }
        // 1. build graph
        for(int i = 0; i < n - 1; i++){
            String w1 = words[i], w2 = words[i + 1];
            int maxLen = Math.max(w1.length(), w2.length());
            for(int j = 0; j < maxLen; j++){
                if(j == w2.length()) return "";//不合法
                if(j == w1.length()) break;
                if(w1.charAt(j) != w2.charAt(j)){
                    char from = w1.charAt(j), to = w2.charAt(j);
                    if(graph.get(from) == null){
                        graph.put(from, new LinkedList<>());
                    }
                    graph.get(from).add(to);
                    break;//找到第一个不同字母，可以判断顺序
                }
            }

        }
        // 2.topological sort
        visited = new boolean[26];
        onPath = new boolean[26];
        path = new StringBuilder();
        for(char ch : graph.keySet()){
            traverse(graph, ch);
        }
        // 3. get final result
        if(hasCycle) return "";//存在环则无法排序出合法的字母顺序
        for(char unk : unknown){
            if(path.indexOf(String.valueOf(unk)) == -1){
                path.append(unk);
            }
        }
        return path.reverse().toString();

    }

    boolean[] visited;//记录结点访问
    boolean[] onPath;//记录路线访问
    boolean hasCycle;//存在环标志
    StringBuilder path;

    void traverse(Map<Character, List<Character>> graph, char ch){
        if(onPath[ch - 'a']) hasCycle = true;//该路径曾经访问过，存在环
        if(hasCycle || visited[ch - 'a']) return; // 存在环或者已访问过该节点 返回
        visited[ch - 'a'] = true;
        onPath[ch - 'a'] = true;
        if(graph.get(ch) != null){
            for(char next : graph.get(ch)){
                traverse(graph, next);
            }
        }
        path.append(ch);
        onPath[ch - 'a'] = false;
    }

}

graph可以用HashMap，也可以沿用之前schedule中的List[]

graph dfs三要素：

  • hasCycle
  • visited[]
  • onPath[]

拓扑排序结果即为后序遍历的逆序

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class LeetCode269 {
    boolean hasCycle;
    boolean[] visited;
    boolean[] onPath;
    StringBuilder sb;
    public String alienOrder(String[] words) {
        Map<Character, List<Character>> graph=new HashMap<>();
        Set<Character> set=new HashSet<>();

        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                set.add(word.charAt(i));
            }
        }

        for (int i = 1; i < words.length; i++) {
            String small=words[i-1];
            String big=words[i];
            int len=Math.max(small.length(),big.length());
            for (int j = 0; j < len; j++) {
                if(j==big.length()){ //invalid
                    return "";
                }
                if(j==small.length()){
                    break;
                }
                if(small.charAt(j)!=big.charAt(j)){
                    char from=small.charAt(j);
                    char to=big.charAt(j);
                    graph.putIfAbsent(from, new ArrayList<>());
                    graph.get(from).add(to);
                    break;
                }
            }
        }

        hasCycle=false;
        visited=new boolean[26];
        onPath=new boolean[26];
        sb=new StringBuilder();
        for (char c : set) {
            dfs(graph,c);
        }
        if(hasCycle){
            return "";
        }
        return sb.reverse().toString();
    }

    void dfs(Map<Character, List<Character>> graph, char cur){
        if(onPath[cur-'a']){
            hasCycle=true;
        }
        if(visited[cur-'a'] || hasCycle){
            return;
        }
        visited[cur-'a']=true;
        onPath[cur-'a']=true;
        if(graph.containsKey(cur)){
            for (char next : graph.get(cur)) {
                dfs(graph,next);
            }
        }
        sb.append(cur);
        onPath[cur-'a']=false;
    }
}

272. Closest Binary Search Tree Value II

Assume that the BST is balanced. Could you solve it in less than O(n) runtime (where n = total nodes)?

k-th smallet elements

法一：traverse + heap, O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
PriorityQueue<Integer> pq;
public List<Integer> closestKValues(TreeNode root, double target, int k) {
    pq=new PriorityQueue<>((a,b)->Math.abs(a-target)<Math.abs(b-target) ? -1 : 1);
    dfs(root);
    List<Integer> res=new ArrayList<>();
    int count=0;
    while(count++<k){
        res.add(pq.poll());
    }
    return res;
}

void dfs(TreeNode root){
    if(root==null){
        return;
    }
    dfs(root.left);
    pq.offer(root.val);
    dfs(root.right);
}

法二：quick select, O(n)

827. Making A Large Island

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class LeetCode827 {
    int row;
    int col;
    int idx;
    int[][] grid;
    int[] area;
    int[] dx;
    int[] dy;
    public int largestIsland(int[][] grid) {
        row=grid.length;
        col=grid[0].length;
        this.grid=grid;
        idx=2;
        dx=new int[]{0,0,1,-1};
        dy=new int[]{1,-1,0,0};
        area=new int[row*col+2];    //存储每个岛屿的面积，岛屿下标从2开始

        int max=Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==1){
                    area[idx]=dfs(i,j);
                    max=Math.max(max,area[idx]);
                    idx++;
                }
            }
        }
        
        //注意去重，同一个岛屿只加一次
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==0){
                    set.clear();
                    int s=1;
                    for (int k = 0; k < 4; k++) {
                        int x=i+dx[k];
                        int y=j+dy[k];
                        if(x<0 || x>=row || y<0 || y>=col || grid[x][y]==0){
                            continue;
                        }
                        if(set.contains(grid[x][y])){
                            continue;
                        }
                        s+=area[grid[x][y]];
                        set.add(grid[x][y]);    //此时grid中存储的已经是岛屿的编号
                    }
                    max=Math.max(max,s);
                }
            }
        }
        return max;
    }

    //计算每个岛屿的面积，并给岛屿编号，同一岛屿编号相同
    int dfs(int i, int j){
        int res=1;
        grid[i][j]=idx;
        for (int k = 0; k < 4; k++) {
            int x=i+dx[k];
            int y=j+dy[k];
            if(x<0 || x>=row || y<0 || y>=col || grid[x][y]!=1){
                continue;
            }
            //等于0说明是水，大于等于2说明已经作为岛屿(的一部分)被计算过了
            res+=dfs(x,y);
        }
        return res;
    }
}

连同的同一个岛屿的idx相同！！

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class LeetCode827 {
    int[][] grid;
    int row;
    int col;
    int[] area;
    int[] dx=new int[]{1,-1,0,0};
    int[] dy=new int[]{0,0,1,-1};
    public int largestIsland(int[][] grid) {
        this.grid=grid;
        row=grid.length;
        col=grid[0].length;
        area=new int[2+row*col];
        int max=Integer.MIN_VALUE;
        int idx=2; //island index starting form 2; 0 for water, 1 for unscanned island
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==1){
                    area[idx]=dfs(i,j,idx);
                    idx++;
                }
            }
        }
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==0){
                    int s=1;
                    set.clear();
                    for (int p = 0; p < 4; p++) {
                        int x=i+dx[p];
                        int y=j+dy[p];
                        if(x<0 || x>=row || y<0 || y>=col || grid[x][y]==0){
                            continue;
                        }
                        int island=grid[x][y];
                        if(set.contains(island)){
                            continue;
                        }
                        set.add(island);
                        s+=area[island];
                    }
                    max=Math.max(max,s);
                }
            }
        }
        return max==Integer.MIN_VALUE ? row*col : max;
    }

    int dfs(int i, int j, int idx){
        grid[i][j]=idx;
        int res=1;
        for (int p = 0; p < 4; p++) {
            int x=i+dx[p];
            int y=j+dy[p];
            if(x<0 || x>=row || y<0 || y>=col || grid[x][y]!=1){
                continue;
            }
            res+=dfs(x,y,idx);
        }
        return res;
    }
}

130. Surrounded Regions

反向flood

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
public class LeetCode130 {
    int row;
    int col;
    public void solve(char[][] board) {
        row=board.length;
        col=board[0].length;
        for (int i = 0; i < row; i++) {
            dfs(board,i,0);
            dfs(board,i,col-1);
        }
        for (int j = 0; j < col; j++) {
            dfs(board,0,j);
            dfs(board,row-1,j);
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }
                if(board[i][j]=='S'){
                    board[i][j]='O';
                }
            }
        }
    }

    void dfs(char[][] board, int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]=='X' || board[i][j]=='S'){
            return;
        }
        board[i][j]='S';
        dfs(board,i-1,j);
        dfs(board,i+1,j);
        dfs(board,i,j-1);
        dfs(board,i,j+1);
    }
}

261. Graph Valid Tree

法一：DFS：

  • 跟有向图不同，无向图dfs要删除回头路
  • 否则会产生unnecessary circle
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
public class LeetCode261 {
    int[][] graph;
    boolean[] visited;
    boolean[] onPath;
    boolean has_cycle;
    int count;
    public boolean validTree(int n, int[][] edges) {
        graph=new int[n][n];
        for (int[] edge : edges) {
            int a=edge[0];
            int b=edge[1];
            graph[a][b]=1;
            graph[b][a]=1;
        }
        visited=new boolean[n];
        onPath=new boolean[n];
        count=0;
        dfs(0);
        return !has_cycle && count==n;
    }

    void dfs(int cur){
        if(onPath[cur]){
            has_cycle=true;
        }
        if(has_cycle || visited[cur]){
            return;
        }
        visited[cur]=true;
        onPath[cur]=true;
        count++;
        for (int i = 0; i < graph[cur].length; i++) {
            if(graph[cur][i]==1){
                graph[i][cur]=0; //avoid unnecessary circle
                dfs(i);
            }
        }
        onPath[cur]=false;
    }
}

法二：UnionFind

113. Path Sum II

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
List<List<Integer>> res;
   int target;
   List<Integer> path;
 public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
     res=new ArrayList<>();
     target=targetSum;
     path=new ArrayList<>();
     dfs(root,0);
     return res;
 }

 void dfs(TreeNode root, int sum){
     if(root==null){
         return;
     }
     if(root.left==null && root.right==null){
         if(sum+root.val==target){
             path.add(root.val);
             res.add(new ArrayList<>(path));
             path.remove(path.size()-1);
         }
         return;
     }
     path.add(root.val);
     dfs(root.left,sum+root.val);
     dfs(root.right,sum+root.val);
     path.remove(path.size()-1);
 }

124. Binary Tree Maximum Path Sum

初代hard题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int res;
public int maxPathSum(TreeNode root) {
    res=Integer.MIN_VALUE;
    dfs(root);
    return res;
}

int dfs(TreeNode root){
    if(root==null){
        return 0;
    }
    int l=Math.max(dfs(root.left),0);
    int r=Math.max(dfs(root.right),0);
    int max=root.val+l+r;
    res=Math.max(res,max);
    return root.val+Math.max(l,r);
}

129. Sum Root to Leaf Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    int res;
    public int sumNumbers(TreeNode root) {
        dfs(root,0);
        return res;
    }

    void dfs(TreeNode cur, int num){
        if(cur==null){
            return;
        }
        if(cur.left==null && cur.right==null){
            num*=10;
            num+=cur.val;
            res+=num;
            return;
        }
        dfs(cur.left,num*10+cur.val);
        dfs(cur.right,num*10+cur.val);
    }
}

230. Kth Smallest Element in a BST

法一：O(H+k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int index;
  int res;
  boolean done;
public int kthSmallest(TreeNode root, int k) {
    index=0;
    res=0;
    dfs(root,k);
    return res;
}

void dfs(TreeNode cur, int k){
    if(cur==null || done){
        return;
    }
    dfs(cur.left,k);
    index++;
    if(index==k){
        done=true;
        res=cur.val;
    }
    dfs(cur.right,k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
  public int kthSmallest(TreeNode root, int k) {
    LinkedList<TreeNode> stack = new LinkedList<>();

    while (true) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      if (--k == 0) return root.val;
      root = root.right;
    }
  }
}

Follow up:

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

257. Binary Tree Paths

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
List<String> res;
  LinkedList<Integer> path;
public List<String> binaryTreePaths(TreeNode root) {
    res=new ArrayList<>();
    path=new LinkedList<>();
    dfs(root);
    return res;
}

void dfs(TreeNode root){
    if(root==null){
        return;
    }
    path.add(root.val);
    if(root.left==null && root.right==null){
        StringBuilder sb=new StringBuilder();
        for (Integer i : path) {
            sb.append(i);
            sb.append("->");
        }
        sb.deleteCharAt(sb.length()-1);
        sb.deleteCharAt(sb.length()-1);
        res.add(sb.toString());
    }
    dfs(root.left);
    dfs(root.right);
    path.removeLast();
}

270. Closest Binary Search Tree Value

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
//1 2 3 4 5
boolean done;
  int start;
  int pre;
  int res;
public int closestValue(TreeNode root, double target) {
    res=Integer.MIN_VALUE;
    pre=Integer.MIN_VALUE;
    dfs(root,target);
    if(done){
        return res;
    }
    return pre<target ? pre : start;
}

void dfs(TreeNode root, double target){
    if(root==null || done){
        return;
    }
    dfs(root.left,target);
    int cur=root.val;
    if(pre!=Integer.MIN_VALUE){
        if(pre<=target && cur>=target){
            if(Math.abs(pre-target)<Math.abs(cur-target)){
                res=pre;
            }else{
                res=cur;
            }
            done=true;
        }
    }else{
        start=cur;
    }
    pre=cur;
    dfs(root.right,target);
}

注意：

1
System.out.println(1==1.0);	//true

298. Binary Tree Longest Consecutive Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int res;
public int longestConsecutive(TreeNode root) {
    dfs(root,0);
    return res;
}

void dfs(TreeNode root, int l){
    if(root==null){
        res=Math.max(res,l);
        return;
    }
    l++;
    res=Math.max(res,l);
    if(root.left!=null && root.val+1==root.left.val){
        dfs(root.left,l);
    }else{
        dfs(root.left,0);
    }
    if(root.right!=null && root.val+1==root.right.val){
        dfs(root.right,l);
    }else{
        dfs(root.right,0);
    }
}

323. Number of Connected Components in an Undirected Graph

法一：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
boolean[] visited;
int[][] graph;
int n;
public int countComponents(int n, int[][] edges) {
    graph=new int[n][n];
    this.n=n;
    for (int[] edge : edges) {
        int a=edge[0];
        int b=edge[1];
        graph[a][b]=1;
        graph[b][a]=1;
    }
    int res=0;
    visited=new boolean[n];
    for (int i = 0; i < n; i++) {
        if(!visited[i]){
            res++;
            dfs(i);
        }
    }
    return res;
}

void dfs(int cur){
    if(visited[cur]){
        return;
    }
    visited[cur]=true;
    for (int i = 0; i < n; i++) {
        if(graph[cur][i]==1){
            graph[i][cur]=0;
            dfs(i);
        }
    }
}

329. Longest Increasing Path in a Matrix

brute force:

(Naive DFS) [Time Limit Exceeded]

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
int[][] matrix;
int row;
int col;
int max;
int[] dx={1,-1,0,0};
int[] dy={0,0,1,-1};
public int longestIncreasingPath(int[][] matrix) {
    this.matrix=matrix;
    row=matrix.length;
    col=matrix[0].length;
    max=1;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            dfs(i,j,1);
        }
    }
    return max;
}

void dfs(int i, int j, int l){
    max=Math.max(max,l);
    for (int k = 0; k < 4; k++) {
        int x=i+dx[k];
        int y=j+dy[k];
        if(x<0 || x>=row || y<0 || y>=col
                || matrix[x][y]<=matrix[i][j]){
            continue;
        }
        dfs(x,y,l+1);
    }
}

Approach #2 (DFS + Memoization) [Accepted]

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

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
int[][] matrix;
int row;
int col;
int[] dx={1,-1,0,0};
int[] dy={0,0,1,-1};
int[][] memo;
public int longestIncreasingPath(int[][] matrix) {
    this.matrix=matrix;
    row=matrix.length;
    col=matrix[0].length;
    memo=new int[row][col];
    int res=1;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            res=Math.max(res,dfs(i,j));
        }
    }
    return res;
}

int dfs(int i, int j){
    if(memo[i][j]!=0){
        return memo[i][j];
    }
    int res=1;
    for (int k = 0; k < 4; k++) {
        int x=i+dx[k];
        int y=j+dy[k];
        if(x<0 || x>=row || y<0 || y>=col
                || matrix[x][y]<=matrix[i][j]){
            continue;
        }
        res=Math.max(res,dfs(x,y)+1);
    }
    memo[i][j]=res;
    return res;
}

333. Largest BST Subtree

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
Map<TreeNode, Integer> maxMap=new HashMap<>();
 Map<TreeNode,Integer> minMap=new HashMap<>();
 Map<TreeNode,Integer> sizeMap=new HashMap<>();


public int largestBSTSubtree(TreeNode root) {
    if(root==null){
        return 0;
    }
    int l=largestBSTSubtree(root.left);
    int r=largestBSTSubtree(root.right);
    int res=Math.max(l,r);
    if(valid(root)){
        res=Math.max(res,size(root.left)+size(root.right)+1);
    }
    return res;
}


boolean valid(TreeNode root){
     if(root==null){
         return true;
     }
     if(root.left!=null && max(root.left)>=root.val){
         return false;
     }
    if(root.right!=null && min(root.right)<=root.val){
        return false;
    }
     boolean l=valid(root.left);
     boolean r=valid(root.right);
     return l&&r;
}

int size(TreeNode root){
     if(root==null){
         return 0;
     }
     if(sizeMap.containsKey(root)){
         return sizeMap.get(root);
     }
     int l=size(root.left);
     int r=size(root.right);
     int res=l+r+1;
     sizeMap.put(root,res);
     return res;
}

int max(TreeNode root){
    if(maxMap.containsKey(root)){
        return maxMap.get(root);
    }
     if(root.left==null && root.right==null){
         return root.val;
     }
     int res=root.val;
     if(root.left!=null){
         res=Math.max(res,max(root.left));
     }
    if(root.right!=null){
        res=Math.max(res,max(root.right));
    }
    maxMap.put(root,res);
    return res;
}

int min(TreeNode root){
    if(minMap.containsKey(root)){
        return minMap.get(root);
    }
    if(root.left==null && root.right==null){
        return root.val;
    }
    int res=root.val;
    if(root.left!=null){
        res=Math.min(res,min(root.left));
    }
    if(root.right!=null){
        res=Math.min(res,min(root.right));
    }
    minMap.put(root,res);
    return res;
}

364. Nested List Weight Sum II

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
int maxDepth=1;
public int depthSumInverse(List<NestedInteger> nestedList) {
    for(NestedInteger i : nestedList){
        maxDepth=Math.max(maxDepth,getMax(i));
    }
    return dfs(nestedList,maxDepth);
}

int dfs(List<NestedInteger> nestedList, int depth){
    int res=0;
    for(NestedInteger i : nestedList){
        if(i.isInteger()){
            res+=i.getInteger()*depth;
        }else{
            res+=dfs(i.getList(),depth-1);
        }
    }
    return res;
}




int getMax(NestedInteger i){
    if(i.isInteger()){
        return 1;
    }
    int depth=1;
    for(NestedInteger next : i.getList()){
        depth=Math.max(depth,getMax(next)+1);
    }
    return depth;
}

366. Find Leaves of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeMap<Integer,List<Integer>> map;
public List<List<Integer>> findLeaves(TreeNode root) {
    map=new TreeMap<>();
    dfs(root);
    return new ArrayList<>(map.values());
}

int dfs(TreeNode cur){
    if(cur==null){
        return -1;
    }
    int l=dfs(cur.left);
    int r=dfs(cur.right);
    int depth=Math.max(l,r)+1;
    map.putIfAbsent(depth,new ArrayList<>());
    map.get(depth).add(cur.val);
    return depth;
}

386. Lexicographical Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<Integer> res=new ArrayList<>();
public List<Integer> lexicalOrder(int n) {
    for (int i = 1; i < 10; i++) {
        dfs(i,n);
    }
    return res;
}

void dfs(int cur, int n){
    if(cur>n){
        return;
    }
    res.add(cur);
    for (int i = 0; i < 10; i++) {
        if(cur*10+i<=n){
            dfs(cur*10+i,n);
        }
    }
}

399. Evaluate Division

Approach 1: Path Search in Graph

注意：

  1. 有向图找路径，用visited去重

  2. 只要找到一条路就可返回

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
49
Map<String, Map<String,Double>> graph;

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    build(equations,values);
    double[] res=new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
        String start=queries.get(i).get(0);
        String end=queries.get(i).get(1);
        res[i]=dfs(start,end,new HashSet<>());
    }
    return res;
}

double dfs(String cur, String end, Set<String> visited){
    if(!graph.containsKey(cur)){
        return -1.0;
    }
    if(cur.equals(end)){
        return 1.0;
    }
    visited.add(cur);
    for (Map.Entry<String, Double> pair : graph.get(cur).entrySet()) {
        String next=pair.getKey();
        if(visited.contains(next)){
            continue;
        }
        double value=pair.getValue();
        double res=dfs(next,end,visited);
        if(res!=-1.0){
            return res*value;
        }
    }
    visited.remove(cur);
    return -1.0;
}

void build(List<List<String>> equations, double[] values){
    graph=new HashMap<>();
    int n=equations.size();
    for (int i = 0; i < n; i++) {
        String dividend=equations.get(i).get(0);
        String divisor=equations.get(i).get(1);
        double value=values[i];
        graph.putIfAbsent(dividend,new HashMap<>());
        graph.putIfAbsent(divisor,new HashMap<>());
        graph.get(dividend).put(divisor,value);
        graph.get(divisor).put(dividend,1/value);
    }
}

Approach 2: Union-Find with Weights

带权并查集

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
  public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    HashSet<String> sHashSet = new HashSet<>();
    for (List<String> List : equations)
      for (String s : List)
        sHashSet.add(s);// 初始化
    UnionFind uf = new UnionFind(sHashSet);
    for (int i = 0; i < values.length; i++) {
      List<String> list = equations.get(i);
      uf.union(list.get(0), list.get(1), values[i]);// 合并
    }
    double[] ans = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
      List<String> list = queries.get(i);
      String s1 = list.get(0);
      String s2 = list.get(1);
      if (uf.find(s1) == null || uf.find(s2) == null)
        ans[i] = -1;
      else if (uf.find(s1).equals(uf.find(s2))) {
        ans[i] = uf.valueMap.get(s1) / uf.valueMap.get(s2);
      } else
        ans[i] = -1;
    }
    return ans;
  }

  class UnionFind {
    private Map<String, String> parent; // 记录每个节点的父节点
    HashMap<String, Double> valueMap = new HashMap<>();// 记录每个string对应的值

    public UnionFind(HashSet<String> StringSet) {
      parent = new HashMap<>();
      for (String s : StringSet) { // 初始化父节点为自身
        parent.put(s, s);
        valueMap.put(s, 1.0);// 初始赋权均为0
      }
    }

    public String find(String x) {
      if (!parent.containsKey(x)) {
        return null;
      }
      String root = x;
      double base = 1;
      while (!root.equals(parent.get(root))) {// 先从x找到根节点，并更新base为到根节点的权重
        root = parent.get(root);
        base *= valueMap.get(root);
      }
      while (!x.equals(root)) {// 更新从x到根节点路径上节点的权重
        String fatherString = parent.get(x);
        valueMap.put(x, valueMap.get(x) * base);
        base /= valueMap.get(fatherString);
        parent.put(x, root);// 压缩路径
        x = fatherString;
      }
      return root;
    }

    public void union(String x, String y, Double value) {
      String rootX = find(x);
      String rootY = find(y);
      if (rootX.equals(rootY)) {
        return;
      }
      parent.put(rootX, rootY);
      valueMap.put(rootX, value * valueMap.get(y) / valueMap.get(x));
    }
  }
}

417. Pacific Atlantic Water Flow

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
int row;
int col;
int[][] heights;

public List<List<Integer>> pacificAtlantic(int[][] heights) {
    this.heights=heights;
    row=heights.length;
    col=heights[0].length;
    boolean[][] pacific=new boolean[row][col];
    boolean[][] atlantic=new boolean[row][col];
    for (int i = 0; i < row; i++) {
        dfs(i,0,heights[i][0],pacific);
        dfs(i,col-1,heights[i][col-1],atlantic);
    }
    for (int j = 0; j < col; j++) {
        dfs(0,j,heights[0][j],pacific);
        dfs(row-1,j,heights[row-1][j],atlantic);
    }
    List<List<Integer>> res=new LinkedList<>();
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(pacific[i][j] && atlantic[i][j]){
                res.add(Arrays.asList(i,j));
            }
        }
    }
    return res;
}

void dfs(int i, int j, int preHeight, boolean[][] visited){
    if(i<0 || i>=row || j<0 || j>=col 
            || visited[i][j] || heights[i][j]<preHeight){
        return;
    }
    visited[i][j]=true;
    dfs(i+1,j,heights[i][j],visited);
    dfs(i-1,j,heights[i][j],visited);
    dfs(i,j+1,heights[i][j],visited);
    dfs(i,j-1,heights[i][j],visited);
}

426. Convert Binary Search Tree to Sorted Doubly Linked 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
Node first;
Node pre;
public Node treeToDoublyList(Node root) {
    if(root==null){
        return null;
    }
    dfs(root);
    first.left=pre;
    pre.right=first;
    return first;
}

void dfs(Node cur){
    if(cur==null){
        return;
    }
    dfs(cur.left);
    if(first==null){
        first=cur;
    }else{
        pre.right=cur;
        cur.left=pre;
    }
    pre=cur;
    dfs(cur.right);
}

430. Flatten a Multilevel Doubly Linked 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
Node pre;
public Node flatten(Node head) {
    dfs(head);
    return head;
}

void dfs(Node cur){
    if(cur==null){
        return;
    }
    pre=cur;
    if(cur.child==null){
        dfs(cur.next);
    }else{
        Node next=cur.next;
        Node child=cur.child;
        dfs(child);
        cur.next=child;
        cur.child=null;
        child.prev=cur;
        pre.next=next;
        if(next!=null){
            next.prev=pre;
        }
        dfs(next);
    }
}

437. Path Sum III

法一：丑陋的brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int target;
int res=0;
public int pathSum(TreeNode root, int targetSum) {
    target=targetSum;
    dfs(root,new ArrayList<>());
    return res;
}

void dfs(TreeNode node, List<Long> sums){
      if(node==null){
          return;
      }
    sums.add((long) 0);
    for (int i = 0; i < sums.size(); i++) {
        sums.set(i,sums.get(i)+node.val);
        if(sums.get(i)==target){
            res++;
        }
    }
    List<Long> clone=new ArrayList<>(sums);
    dfs(node.left,sums);
    dfs(node.right,clone);
}

法二：优雅的brute force

1
2
3
4
5
6
7
8
9
10
public int pathSum(TreeNode root, long sum) {
    if (root == null) return 0;
    return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

private int pathSumFrom(TreeNode node, long sum) {
    if (node == null) return 0;
    return (node.val == sum ? 1 : 0) 
        + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
}

490. The Maze

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
int row;
int col;
int[][] maze;
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    row=maze.length;
    col=maze[0].length;
    this.maze=maze;
    return dfs(start[0],start[1],destination,new boolean[row][col]);
}

boolean dfs(int i, int j, int[] end,boolean[][] visited){
    if(i==end[0] && j==end[1]){
        return true;
    }
    visited[i][j]=true;
    for (int[] dir : dirs) {
        int x=i+dir[0];
        int y=j+dir[1];
        while(x>=0 && x<row && y>=0 && y<col && maze[x][y]==0){
            x+=dir[0];
            y+=dir[1];
        }
        if(!visited[x-dir[0]][y-dir[1]]){
            if(dfs(x-dir[0],y-dir[1],end,visited)){
                return true;
            }
        }
    }
    return false;
}
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
Map<Integer,List<Integer>> grid;
List<Integer> list;
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
    grid=new HashMap<>();
    int n=pid.size();
    for (int i = 0; i < n; i++) {
        int to=pid.get(i);
        int from=ppid.get(i);
        grid.putIfAbsent(from,new ArrayList<>());
        grid.get(from).add(to);
    }
    list=new ArrayList<>();
    list.add(kill);
    dfs(kill);
    return list;
}

void dfs(int cur){
    if(grid.containsKey(cur)){
        for (Integer next : grid.get(cur)) {
            //不存在环，无需判断contains
            //list.contains低效，加了会超时
                list.add(next);
                dfs(next);
        }
    }
}