## 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

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

### Analysis:

The basic idea is still traversing the binary tree in level order (up-down). We can just use a vector to store the nodes and its level, set a pointer, each time move forward one and push its children into the vector. When all the nodes are visited, the vector become the up-down nodes in level order with level information. A simple loop can handle the output requirement.Details can be easily found in the code below.

The complexity is O(n), n is the number of nodes in the binary tree.

### Code(C++):

/** * 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) { if (!root) {return vector<vector<int> >();} vector<pair<TreeNode*,int> > q; int lev=1; int count=0; q.push_back(make_pair(root,lev)); while (count<q.size()){ TreeNode *node = q[count].first; lev = q[count].second; if (node->left){ q.push_back(make_pair(node->left,lev+1));} if (node->right){ q.push_back(make_pair(node->right,lev+1));} count++; } vector<vector<int> > res(lev, vector<int>()); for (int i=0;i<q.size();i++){ res[lev-q[i].second].push_back(q[i].first->val); } return res; } };

### Code(Python):

# Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a list of lists of integers def levelOrderBottom(self, root): res = [] if root == None: return res q = [] q.append([root, 1]) while len(q) != 0: node, dep = q.pop() if len(res) < dep: res.append([node.val]) else: res[dep-1].append(node.val) if node.right != None: q.append([node.right, dep + 1]) if node.left != None: q.append([node.left, dep + 1]) return res[::-1]

We can also reverse the vector directly as

ReplyDeletereverse(res.begin(),res.end());