Java O(n) concise solution with explanation

  • 0
    // let the height of node is the round that we remove the node.(e.g. all the leaves have a height of 0)
    // we can know the height of each node only when we reach the leaf and go back
    // therefore when we go back from the leaf to its parant, we collect leaves and put it into a corresponding list.
    // note that the height of the parent is equal to the max height of its children + 1.
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) return res;
        findLeaves(root, res);
        return res;
    private int findLeaves(TreeNode root, List<List<Integer>> res){
        int h = -1;
        if (root.left != null) h = findLeaves(root.left, res);
        if (root.right != null) h = Math.max(h, findLeaves(root.right, res));
        List<Integer> list = null;
        if (res.size() - 1 < h) {
            list = new ArrayList<Integer>();
        else list = res.get(h);
        return h;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.