366. Find Leaves of Binary Tree

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. Example: Given binary tree

          1
         / \
        2   3
       / \     
      4   5    

Returns [4, 5, 3], [2], [1].

Solution1: 포스트-order Divide & Conquer Bottom-up 상향 전달

생각: ● Divide 좌우 트리, Conquer leaf 최대 거리 구하기 max_dist를 위로 전달하고 result_에 추가합니다.list1a는 먼저 하이트를 구하여 고정된 길이의 결과를 만들었다.하지만 사실은 안 써도 돼요. 사실 훑어보는 순서에 따라 최대 거리가 일정한 연속으로 늘어나면result_list, 매번 초과 후 동적 증가하면 됩니다. 예를 들어 쓰기 2a.Time Complexity: O(N) Space Complexity: O(N) 귀속 캐시
Solution1a Code:

class Solution {
    public List> findLeaves(TreeNode root) {
        // build result list
        int height = getMaxHeight(root);
        List> result = new ArrayList>();
        for(int i = 0; i < height; i++) result.add(new ArrayList());
        
        // bottom-up dfs
        dfsHelper(result, root);
        return result;
    }
    private int dfsHelper(List> result, TreeNode node) {
        if(node == null) return -1;
            
        int max_dist = 1 + Math.max(dfsHelper(result, node.left), dfsHelper(result, node.right));
        result.get(max_dist).add(node.val);
        
        return max_dist;
    }
    
    private int getMaxHeight(TreeNode root) {
        if(root == null) return 0;
        return 1 + Math.max(getMaxHeight(root.left), getMaxHeight(root.right));
    }
}

Solution2a Code:

class Solution {
    public List> findLeaves(TreeNode root) {
        List> result = new ArrayList<>();
        if(root == null) return result;
        dfs(root, result);
        return result;
    }
    private int dfs(TreeNode node, List> result) {
        if(node == null) return 0;
        int left_d = dfs(node.left, result);
        int right_d = dfs(node.right, result);
        
        int level = Math.max(left_d, right_d) + 1;
        if(level > result.size()) result.add(new ArrayList<>());
        
        result.get(level - 1).add(node.val);
        return level;
    }
}