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]]
confused what "{1,#,2,3}" means?
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1 / \ 2 3 / 4 \ 5The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}". 解法一：递归
参考了Discussion中stellari的做法，递归进行层次遍历，并将每个level对应于相应的vector。
/** * 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 > result; void levelTra(TreeNode *root, int level) { if(root == NULL) return; if(level == result.size()) { vector v; result.push_back(v); } result[level].push_back(root->val); levelTra(root->left, level+1); levelTra(root->right, level+1); } vector > levelOrderBottom(TreeNode *root) { levelTra(root, 0); return vector >(result.rbegin(), result.rend()); }}; 
解法二：普通层次遍历后逆序。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ struct Node{ TreeNode* tNode; int level; Node(TreeNode* newtNode, int newlevel): tNode(newtNode), level(newlevel) {}};class Solution {public: vector > levelOrderBottom(TreeNode *root) { vector > ret; if(!root) return ret; // push root Node* rootNode = new Node(root, 0); queue Nqueue; Nqueue.push(rootNode); vector cur; int curlevel = 0; while(!Nqueue.empty()) { Node* frontNode = Nqueue.front(); Nqueue.pop(); if(frontNode->level > curlevel) { ret.push_back(cur); cur.clear(); curlevel = frontNode->level; } cur.push_back(frontNode->tNode->val); if(frontNode->tNode->left) { Node* leftNode = new Node(frontNode->tNode->left, frontNode->level+1); Nqueue.push(leftNode); } if(frontNode->tNode->right) { Node* rightNode = new Node(frontNode->tNode->right, frontNode->level+1); Nqueue.push(rightNode); } } ret.push_back(cur); reverse(ret.begin(), ret.end()); return ret; }}; 