# 366\. Find Leaves of Binary Tree


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findLeaves(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        result = [[]  for _ in range(100)]
        
        def dfs_height(node): # dfs
            if not node:  # Define NIL as height 0
                return 0
            height_this_node = max(dfs_height(node.left), dfs_height(node.right)) + 1
            result[height_this_node - 1].append(node.val)
            return height_this_node
        
        dfs_height(root)        

        while result[-1] == []:
            result.pop()

        return result

    
class Solution:
    def findLeaves(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        result = [[]  for _ in range(100)]
        
        def dfs_height(node): # dfs
            if not node:  # Define NIL as height -1
                return -1
            height_this_node = max(dfs_height(node.left), dfs_height(node.right)) + 1
            result[height_this_node].append(node.val)
            return height_this_node
        
        dfs_height(root)        

        while result[-1] == []:
            result.pop()

        return result

    
class Solution:
    def findLeaves(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        node_value_by_height = defaultdict(list)
        
        def dfs_height(node): # dfs
            if not node:  # Define NIL as height 0
                return 0
            height_this_node = max(dfs_height(node.left), dfs_height(node.right)) + 1
            node_value_by_height[height_this_node].append(node.val)
            return height_this_node
        
        dfs_height(root)        
        
        max_height = max(node_value_by_height.keys())
        result = []
        for height in range(1, max_height + 1):
            result.append(node_value_by_height[height])

        return result
    
"""Best"""
class Solution:
    def findLeaves(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        
        def dfs_height(node): # dfs
            if not node:  # Define NIL as height -1
                return -1
            height_this_node = max(dfs_height(node.left), dfs_height(node.right)) + 1
            
            """
            There will not be no skips when encountering height_this_node when DFSl
            When you see a new hieght, it must be previous max height + 1.
            """
            if height_this_node >= len(result):
                result.append([node.val])
            else:
                result[height_this_node].append(node.val)
            return height_this_node
        
        dfs_height(root)        

        return result