【LeetCode】107. Binary Tree Level Order Traversal II

LeetCode-107

Links:https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

/ \

9 20

/ \

15 7

return its bottom-up level order traversal as:

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

[

[15,7],

[9,20],

[3]

]

方法1：递归层序遍历，然后返回rbegin，rend…

/**
 * 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>> levelOrderBottom(TreeNode* root) {
        levelSearch(root,0);
        return vector<vector<int>>(nums.rbegin(),nums.rend());
    }
};

/**

* 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>> levelOrderBottom(TreeNode* root) {

levelSearch(root,0);

return vector<vector<int>>(nums.rbegin(),nums.rend());

}

};

方法2：循环.

思路：用queue的特性，一层一层的访问。

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

/**

* 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>> levelOrderBottom(TreeNode* root) {

vector<vector<int>> nums;

if(root==NULL)return nums;

queue<TreeNode*>q;

q.push(root);

while(q.size()>0)

{

queue<TreeNode*>q_temp;

vector<int>nums_temp;

while(q.size()>0)

{

TreeNode* temp = q.front();

q.pop();

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

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

nums_temp.push_back(temp->val);

}

q = q_temp;

nums.push_back(nums_temp);

}

return vector<vector<int>>(nums.rbegin(),nums.rend());

}

};

【LeetCode】107. Binary Tree Level Order Traversal II

Tagged on: LeetCode