package com.freetymekiyan.algorithms.level.medium;

import com.freetymekiyan.algorithms.utils.Utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until
 * the tree is empty.
 * <p>
 * Example:
 * Given binary tree
 * 1
 * / \
 * 2   3
 * / \
 * 4   5
 * Returns [4, 5, 3], [2], [1].
 * <p>
 * Explanation:
 * 1. Removing the leaves [4, 5, 3] would result in this tree:
 * <p>
 * 1
 * /
 * 2
 * 2. Now removing the leaf [2] would result in this tree:
 * <p>
 * 1
 * 3. Now removing the leaf [1] would result in the empty tree:
 * <p>
 * []
 * Returns [4, 5, 3], [2], [1].
 * <p>
 * Company Tags: LinkedIn
 * Tags: Tree, Depth-first Search
 */
public class FindLeavesOfBinaryTree {

    /**
     * Tree, DFS(Backtracking).
     * Make use of one property of tree node, its height.
     * Height is the number of edges from the node to the deepest leaf.
     * So leaf node will have height 0.
     * This problem is just aggregating all nodes with same height into a list.
     */
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        height(root, res);
        return res;
    }

    /**
     * Return the height of a node.
     * height(node) = 1 + max(height(node.left), height(node.right))
     */
    private int height(TreeNode node, List<List<Integer>> res) {
        if (null == node) return -1;
        int level = 1 + Math.max(height(node.left, res), height(node.right, res));
        if (res.size() == level) { // Current level exceeds result list size
            res.add(new ArrayList<>());
        }
        res.get(level).add(node.val);
        // root.left = root.right = null;
        return level;
    }
}

@@ -347,19 +347,34 @@
 %0A * 
-1%0A *
+%7C     1%0A * %7C   
  / %5C%0A *
+ %7C  
  2  
@@ -378,23 +378,28 @@
 2   3%0A *
+ %7C 
  / %5C%0A *
+ %7C
  4   5%0A 
@@ -528,18 +528,27 @@
 %3E%0A *
+ %7C  
  1%0A *
+ %7C 
  /%0A *
+ %7C
  2%0A 
@@ -614,16 +614,18 @@
 * %3Cp%3E%0A *
+ %7C
  1%0A * 3.
@@ -928,17 +928,20 @@
 de, its 
-h
+getH
 eight.%0A 
@@ -1041,17 +1041,20 @@
 ll have 
-h
+getH
 eight 0.
@@ -1114,17 +1114,20 @@
 th same 
-h
+getH
 eight in
@@ -1265,17 +1265,20 @@
         
-h
+getH
 eight(ro
@@ -1340,17 +1340,20 @@
 urn the 
-h
+getH
 eight of
@@ -1368,17 +1368,48 @@
 %0A     * 
-h
+Recurrence relation:%0A     * getH
 eight(no
@@ -1418,25 +1418,28 @@
 ) = 1 + max(
-h
+getH
 eight(node.l
@@ -1444,17 +1444,20 @@
 .left), 
-h
+getH
 eight(no
@@ -1467,16 +1467,80 @@
 right))%0A
+     * Base case:%0A     * If node is null, it's getHeight is -1.%0A
      */%0A
@@ -1555,17 +1555,20 @@
 ate int 
-h
+getH
 eight(Tr
@@ -1632,16 +1632,30 @@
 == node)
+ %7B%0A           
  return 
@@ -1670,17 +1670,28 @@
     
-int level
+%7D%0A        int height
  = 1
@@ -1702,17 +1702,20 @@
 ath.max(
-h
+getH
 eight(no
@@ -1729,17 +1729,20 @@
 , res), 
-h
+getH
 eight(no
@@ -1784,21 +1784,22 @@
 ze() == 
-level
+height
 ) %7B // C
@@ -1805,21 +1805,22 @@
 Current 
-level
+height
  exceeds
@@ -1836,16 +1836,17 @@
 ist size
+.
 %0A       
@@ -1904,21 +1904,22 @@
 res.get(
-level
+height
 ).add(no
@@ -1984,21 +1984,22 @@
  return 
-level
+height
 ;%0A    %7D%0A

update find leaves of binary tree