leetcode 102. Binary Tree Level Order Traversal

Seawolf

1. Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
   
2. 
   
3. For example:
   
4. Given binary tree [3,9,20,null,null,15,7],
   
5.     3
   
6.    / \
   
7.   9  20
   
8.     /  \
   
9.    15   7
   
10. return its level order traversal as:
    
11. [
    
12.   [3],
    
13.   [9,20],
    
14.   [15,7]
    
15. ]

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     vector<vector<int>> levelOrder(TreeNode* root) {
    
13.         // return BFS(root);  
    
14.         vector<vector<int>> ans;
    
15.         DFS(root,0, ans);
    
16.         return ans;
    
17.     }
    
18. 
    
19. private:
    
20.     vector<vector<int>> BFS(TreeNode* root){
    
21.         vector<vector<int>> ans;
    
22.         if(root == NULL) return ans;
    
23.         vector<TreeNode*> cur, next;
    
24.         cur.push_back(root);
    
25.         
    
26.         while(!cur.empty()){
    
27.             ans.push_back({});
    
28.             for(TreeNode* node : cur){
    
29.                 ans.back().push_back(node->val);
    
30.                
    
31.                 if(node->left != NULL) next.push_back(node->left);
    
32.                 if(node->right != NULL) next.push_back(node->right);
    
33.             }
    
34.             
    
35.             cur.swap(next);
    
36.             next.clear();
    
37.         }
    
38.         
    
39.         return ans;
    
40.     }
    
41.    
    
42.     void DFS(TreeNode* root , int depth, vector<vector<int>>& ans){
    
43.         if(root == NULL) return;
    
44.         while(ans.size() <= depth) ans.push_back({});
    
45.         DFS(root->left,depth+1, ans);
    
46.         DFS(root->right,depth+1,ans);
    
47.         ans[depth].push_back(root->val);
    
48.     }
    
49. };

复制代码

optimized DFS

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     vector<vector<int>> levelOrder(TreeNode* root) {
    
13.         // return BFS(root);  
    
14.         vector<vector<int>> ans;
    
15.         if(!root) return ans;
    
16.         DFS(root,0, ans);
    
17.         return ans;
    
18.     }
    
19. 
    
20. private:
    
21.     void DFS(TreeNode* root , int depth, vector<vector<int>>& ans){
    
22.         if(root != NULL) {
    
23.             if(ans.size() > depth){
    
24.                 ans[depth].push_back(root->val);
    
25.             }else{
    
26.                 ans.push_back(vector <int>{root->val});
    
27.             }
    
28.             DFS(root->left, depth+1, ans);
    
29.             DFS(root->right,depth+1, ans);
    
30.         }
    
31.     }
    
32. };

复制代码