2015年6月30日星期二

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
Have you met this question in a real interview? 
Yes
Example
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

Challenge
Challenge 1: Using only 1 queue to implement it.
Challenge 2: Use DFS algorithm to do it.

It has two basic way: BFS and DFS.

For BFS, the typical way is to use pair to record the level of each node and store them in a queue.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        queue<pair<TreeNode*,int>> Q;
        vector<int> tempresult;
        Q.push(make_pair(root,0));
        int pre_lev=0;
        while(!Q.empty()){
            TreeNode *cur=Q.front().first;
            int cur_lev=Q.front().second;
            if(cur_lev>pre_lev){
                result.push_back(tempresult);
                tempresult.clear();
                pre_lev=cur_lev;
            }
            tempresult.push_back(cur->val);
            if(cur->left!=NULL) {
                Q.push(make_pair(cur->left,cur_lev+1));
            
            }
            if(cur->right!=NULL) {
                Q.push(make_pair(cur->right,cur_lev+1));
            }
            Q.pop();
        }
        result.push_back(tempresult);
        return result;
    }
};

Since we don't need to know the exact level of each node in this problem, we can use two queues to record nodes of the same level.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        queue<TreeNode*> q1, q2;
        q1.push(root);
        while(!q1.empty() || !q2.empty()){
            //if(q1.empty) 
            if(q1.empty()){
                q1=q2;
                while(!q2.empty()) q2.pop();
                //no clear() function in queue, has to use this way to clear
                //easy understanding, but cannot pass for time limit
                /*queue<TreeNode*> q3;  
                q3=q1;
                q1=q2;
                q2=q3;*/
            }
            int size=q1.size();
            vector<int> result_temp;
            for(int i=0;i<size;i++){
                TreeNode* cur=q1.front();
                q1.pop();
                result_temp.push_back(cur->val);
                if(cur->left!=NULL) q2.push(cur->left);
                if(cur->right!=NULL) q2.push(cur->right);
            }
            result.push_back(result_temp);
            result_temp.clear();
        }
        return result;
    }
};

For DFS, just do recursion in preorder, which makes it easy to write values in two dimensional vector.

My way is a little tricky.  No initialization for two dimensional vector and no integer to record level. Here is a link to standard DFS solution: http://siddontang.gitbooks.io/leetcode-solution/content/tree/binary_tree_level_order_traversal.html
The main difference is that the standard way has two DFS process, one is used to calculate levels.


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




Reference:
Yu's coding garden--great explanation for BFS
YouTube video: Great basic concepts explanation




Lintcode second:
 BFS
use a queue store nodes and an integer record level size
Time: O(n)
Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        vector<vector<int> > res;
        vector<int> temp;
        queue<TreeNode *> q;
        if(root) q.push(root);
        int levelsize= 1;
        while(!q.empty()){
            TreeNode *cur = q.front();
            q.pop();
            levelsize--;
            temp.push_back(cur->val);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
            
            if(levelsize == 0){
                levelsize = q.size();
                res.push_back(temp);
                temp.clear();
            }
        }
        return res;
    }
};
发帖者 时间：
标签：

没有评论:

发表评论

订阅： 博文评论 (Atom)