Friday, February 6, 2015

LeetCode [102] 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).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]
 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * 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>> ret;
        helper(ret, 0, root);
        return ret;
    }
    
    void helper(vector<vector<int>>& ret, int level, TreeNode* node){
        if(!node) return;
        if(ret.size()<level+1){
            ret.resize(level+1);
        }
        ret[level].push_back(node->val);
        helper(ret, level+1, node->left);
        helper(ret, level+1, node->right);
    }
};

<script class="brush: js" type="syntaxhighlighter"><![CDATA[
/**
 * 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>> ret;
        if(!root) return ret;
        
        queue<TreeNode*> que, que_tmp;
        que.push(root);
        vector<int> layer;
        while(!que.empty()){
            TreeNode *node = que.front();
            layer.push_back(node->val);
            que.pop();
            if(node->left) que_tmp.push(node->left);
            if(node->right) que_tmp.push(node->right);            
            if(que.empty()){
                ret.push_back(layer);
                layer.clear();
                que = que_tmp;
                que_tmp = queue<TreeNode*>();
            }
        }
        return ret;
    }
};

No comments:

Post a Comment