首页 > 代码库 > Binary Tree Level Order Traversal II

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},

    3   /   9  20    /     15   7

 

return its bottom-up level order traversal as:

[  [15,7],  [9,20],  [3]]
/** * Definition for binary tree * 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> > vec;        if(root == NULL) return vec;        queue<TreeNode *> crt, wait;        crt.push(root);        while(crt.size() > 0){            int num = crt.size();            vector<int> arr;            while(num--){                TreeNode *tmp = crt.front();                if(tmp->left) wait.push(tmp->left);                if(tmp->right) wait.push(tmp->right);                arr.push_back(tmp->val);                crt.pop();            }            vec.insert(vec.begin(), arr);            int n = wait.size();            while(n--){                TreeNode *tmp = wait.front();                wait.pop();                crt.push(tmp);            }        }        return vec;    }};

 

Binary Tree Level Order Traversal II