LintCode (70) 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).

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 bottom-up level order traversal as:

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

Tags Expand  


和上面题一样，只是记得push_back改insert front...其实还有那种劳什子的所谓zig zag的。。。。就是需要额外记录下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 44

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { /** * @param root : The root of binary tree. * @return : buttom-up level order a list of lists of integer */ public: vector<vector<int>> levelOrderBottom(TreeNode *root) { // write your code here vector< vector<int>> res; if (!root) return res; queue<TreeNode*> q; q.push(root); while(!q.empty()){ int size=q.size(); vector<int> one; for (int i=0; i<size; i++){ TreeNode* tmp=q.front(); q.pop(); one.push_back(tmp->val); if (tmp->left) q.push(tmp->left); if (tmp->right) q.push(tmp->right); } res.insert(res.begin(),one); } return res; } };