# 366. Find Leaves of Binary Tree

###### tags: `leetcode` `tree` `366` `medium` `rewrite` `DFS`

## :memo: Question

## :memo: 題意
:bulb: 給你一個 tree，請你將 leaf 塞到 list[0] 裡，然後再將下一次的 leaf 塞到 list[1]．．．以此類推

## :memo: leetcode solution
* :medal: **思考一**: 那個的話就可以從 leaf 往上走算他的深度。
以這個圖為例子，node 4 5 3 為深度 0 所以都是第一層的 leaf，因此可以將其塞到 list[0]，node 2 為深度 1 因此可以將其塞到 list[1]，那 node 1 的 leftchild 給的值為 2，rightchild 給的值為 1，要選較大的那個值當深度，因此將其塞到 list[2]。
* :medal: **思考二**: 由上面的例子說明，leftchild 和 rightchild 要各給一個深度的值，然後選擇其較大的值。
* :medal: **思考三**: 題目給的 ans 是有順序性的由左至右，因此要先從 leftchild 遍歷。

# 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]]:
        ans = []
        self.dfs(root, ans)
        return ans
        
    def dfs(self, root, ans):
        if not root:
            return 0
        
        left = self.dfs(root.left, ans)
        right = self.dfs(root.right, ans)
        value = max(left, right) 
        
        if len(ans) <= value:
            ans.append([])
            
        ans[value].append(root.val)
        
        return max(left, right) + 1

## :memo: bigO
* 時間複雜度: O(n)，n = 有幾個 node
* 空間複雜度: O(n)，the space used by solution array.