102

這題算是因緣際會寫到的，原本是要寫第101題的iterative版本，突然聯想到iterative版本就很像在做level order traversal，所以就來寫一下這題。

這題的想法很直觀，既然要把每一層的val都輸出，那就先把每一層的node都先塞到一個vector(level_list)裡面，然後再把同一層的每一個node的val塞到一個vector(val_vec)裡面，然後每一次迴圈都把一層的val_vec塞進ans裡，最後return ans即可。

實作出來的code就會是

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        vector<TreeNode*> level_list, next_level_list;
        vector<int> val_vec;

        if(root == NULL)
            return ans;
        else
            level_list.push_back(root);

        while(level_list.size() != 0)
        {
            val_vec.clear();

            for(int i=0; i<level_list.size(); i++)
                val_vec.push_back(level_list[i]->val);

            ans.push_back(val_vec);


            next_level_list.clear();
            for(int i=0; i<level_list.size(); i++)
            {
                if(level_list[i]->left != NULL)
                    next_level_list.push_back(level_list[i]->left);
                if(level_list[i]->right != NULL)
                    next_level_list.push_back(level_list[i]->right);
            }
            level_list = next_level_list;
        }

        return ans;
    }
};

Java版本：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        /*
        Concept:
        create a List<List<Integer>> res to save results
        create a List<TreeNode> levelList to save TreeNodes of current level.
        levelList.add(root);
        while(levelList.size()!=0){
            add levelList to res
            List<TreeNode> nextLevelList to save node of next level
            for each TreeNode in levelList,
                if node.right exists
                    add node.right to levelList
                if node.left exists
                    add node.right to levelList

            levelList = nextLevelList;
        }
        return res
        */
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        List<TreeNode> levelList = new ArrayList<>();
        levelList.add(root);
        while(levelList.size()!=0){
            List<Integer> valueList = new ArrayList<>();
            for(int i=0; i<levelList.size(); i++){
                valueList.add(levelList.get(i).val);
            }
            res.add(valueList);
            List<TreeNode> nextLevelList = new ArrayList<>();
            for(int i=0; i<levelList.size(); i++){ //each TreeNode in levelList,
                TreeNode node = levelList.get(i);
                if(node.left!=null)
                    nextLevelList.add(node.left);
                if(node.right!=null)
                    nextLevelList.add(node.right);
            }
            levelList = nextLevelList;
        }
        return res;
    }
}