repl.it
@shachopin/

Find Leaves of Binary Tree

Java

No description

fork
loading
Files
  • Main.java
  • jdt.ls-java-project
Main.java
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
class Main {
  public static void main(String[] args) {
    System.out.println("Hello world!");
  }
}

MySolution on lintcode 650 Find Leaves of Binary Tree

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: the root of binary tree
     * @return: collect and remove all leaves
     */
    public List<List<Integer>> findLeaves(TreeNode root) {
        // write your code here
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> ans = new ArrayList<>();
        int height = getHeight(root, map);
        for (int i = 1; i <= height; i++) {
            ans.add(map.get(i));
        }
        return ans;
    }
    
    private int getHeight(TreeNode root, Map<Integer, List<Integer>> map) {
        if (root == null) {
            return 0;
        }
        int height =  Math.max(getHeight(root.left, map), getHeight(root.right, map)) + 1;
        map.putIfAbsent(height, new ArrayList<Integer>());
        map.get(height).add(root.val);
        return height;
    }
}

======================================

official solution:
public class Solution {
    /**
     * @param root the root of binary tree
     * @return collect and remove all leaves
     */
    
    int dfs(TreeNode cur, Map<Integer, List<Integer>> depth) {
        if (cur == null) {
            return 0;
        }
        int d = Math.max(dfs(cur.left, depth), dfs(cur.right, depth)) + 1;

        depth.putIfAbsent(d, new ArrayList<>());
        depth.get(d).add(cur.val);
        return d;
    }

    public List<List<Integer>> findLeaves(TreeNode root) {
        // Write your code here
        List<List<Integer>> ans = new ArrayList<>();

        Map<Integer, List<Integer>> depth = new HashMap<>();
        int max_depth = dfs(root, depth);

        for (int i = 1; i <= max_depth; i++) {
            ans.add(depth.get(i));
        }
        return ans;
    }
}