【LeetCode】102. Binary Tree Level Order Traversal

LeetCode-102

Links:https://leetcode.com/problems/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,#,#,15,7},

/ \

9 20

/ \

15 7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

[

[3],

[9,20],

[15,7]

]

和107题大致一样…就是正向和反向罢了…

代码如下：

深度搜索：

/**
 * 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>>nums;
    void levelSearch(TreeNode* root,int level)
    {
        if(root==NULL){
            return ;
        }
        else{
            if(level == nums.size())
            {
                vector<int>temp;
                temp.push_back(root->val);
                nums.push_back(temp);
            }
            else{
                nums[level].push_back(root->val);
            }
            
            levelSearch(root->left,level+1);
            levelSearch(root->right,level+1);
        }
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        levelSearch(root,0);
        return move(nums);
    }
};

/**

* 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>>nums;

void levelSearch(TreeNode* root,int level)

{

if(root==NULL){

return ;

}

else{

if(level == nums.size())

{

vector<int>temp;

temp.push_back(root->val);

nums.push_back(temp);

}

else{

nums[level].push_back(root->val);

}

levelSearch(root->left,level+1);

levelSearch(root->right,level+1);

}

vector<vector<int>> levelOrder(TreeNode* root) {

levelSearch(root,0);

return move(nums);

}

};

广度搜索：

/**
 * 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>>nums;
        if(root==NULL)return nums;
        queue<TreeNode*>q;
        q.push(root);
        while(q.size()>0)
        {
            vector<int>nums_temp;
            queue<TreeNode*>q_temp;
            while(q.size()>0)
            {
                TreeNode* temp = q.front();
                nums_temp.push_back(temp->val);
                if(temp->left!=NULL)q_temp.push(temp->left);
                if(temp->right!=NULL)q_temp.push(temp->right);
                q.pop();
            }
            q = move(q_temp);
            nums.push_back(move(nums_temp));
        }
        return move(nums);
    }
};

/**

* 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>>nums;

if(root==NULL)return nums;

queue<TreeNode*>q;

q.push(root);

while(q.size()>0)

{

vector<int>nums_temp;

queue<TreeNode*>q_temp;

while(q.size()>0)

{

TreeNode* temp = q.front();

nums_temp.push_back(temp->val);

if(temp->left!=NULL)q_temp.push(temp->left);

if(temp->right!=NULL)q_temp.push(temp->right);

q.pop();

}

q = move(q_temp);

nums.push_back(move(nums_temp));

}

return move(nums);

}

};

【LeetCode】102. Binary Tree Level Order Traversal

Tagged on: LeetCode