LeetCode 107. Binary Tree Level Order Traversal II（二叉樹的層次周遊）

題目

解析

分析：這題需要通路到每個元素，然後還需要按照層次來輸出一個List的兩重嵌套。我想到的方法是用遞歸，對二叉樹先根周遊，遞歸可以較快地不重複地通路每個元素，同時可以通過一個level參數來标記不同的層次，以便把資料分揀到不同的List。用ArrayList來儲存資料，在遞歸的時候會根據通路的深度為第一層的List添加子List，然後根據深度，擷取子List，配置設定val值。因為低層的List靠前，最後使用Collections的反轉。

算法實作：

class Solution {
	List<List<Integer>> list=new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {   
           find(root, 0);
           Collections.reverse(list);
           return list;          
    }        
    public void find(TreeNode root,int level){
    	if(root==null)
    		return;
    	if(list.size()-1<level)
    		list.add(new ArrayList<>());
        list.get(level).add(root.val);    	
    	if(root.left!=null){
    		find(root.left,level+1);
    	}     	
    	if(root.right!=null){
    		find(root.right,level+1);
    	}    	
    }        
}