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] ]
依旧是层序遍历而已,更另一篇博客一样,bfs或者dfs之后reverse一下就可以了,这里给出bfs版本,dfs见另一篇博文:
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 private: 12 struct Node{ 13 TreeNode * treeNode; 14 int level; 15 Node(){} 16 Node(TreeNode * nd, int lv) 17 :treeNode(nd), level(lv){} 18 }; 19 public: 20 vector<vector<int>> levelOrderBottom(TreeNode* root) { 21 vector<vector<int>> ret; 22 if(!root) 23 return ret; 24 queue<Node> nodeQueue; 25 nodeQueue.push(Node(root, 0)); 26 int dep = -1; 27 while(!nodeQueue.empty()){ 28 Node node = nodeQueue.front(); 29 if(node.treeNode->left) 30 nodeQueue.push(Node(node.treeNode->left, node.level + 1)); 31 if(node.treeNode->right) 32 nodeQueue.push(Node(node.treeNode->right, node.level + 1)); 33 if(dep == node.level) 34 ret[dep].push_back(node.treeNode->val); 35 else{ 36 vector<int> tmp; 37 dep++; 38 ret.push_back(tmp); 39 ret[dep].push_back(node.treeNode->val); 40 } 41 nodeQueue.pop(); //不要忘了 42 } 43 reverse(ret.begin(), ret.end()); 44 return ret; 45 } 46 };
LeetCode OJ:Binary Tree Level Order Traversal II(二叉树的层序遍历)
原文:http://www.cnblogs.com/-wang-cheng/p/4905740.html