大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
创新互联是一家专业的成都网站建设公司,我们专注成都网站设计、做网站、网络营销、企业网站建设,友情链接,一元广告为企业客户提供一站式建站解决方案,能带给客户新的互联网理念。从网站结构的规划UI设计到用户体验提高,创新互联力求做到尽善尽美。
例如:
给定二叉树 [3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7
返回其自底向上的层次遍历为:
[ [15,7], [9,20], [3] ]
解题思路:首先temp临时记录层次遍历每一层的结点值,当遍历到下一层的结点时就将temp记录到result中.
代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector> levelOrderBottom(TreeNode* root) {
vector > result; //记录每一层的节点值
if(root == NULL)
return result;
queue > Queue;
vector temp; //临时记录每一层的节点值
Queue.push(make_pair(root,0));
while(!Queue.empty())
{
TreeNode* node = Queue.front().first;
int step = Queue.front().second;
Queue.pop();
if(result.size() == step - 1)
{
result.push_back(temp);
temp.clear();
temp.push_back(node->val);
}
else
{
temp.push_back(node->val);
}
if(node->left)
Queue.push(make_pair(node->left, step + 1));
if(node->right)
Queue.push(make_pair(node->right, step + 1));
}
result.push_back(temp);
reverse(result.begin(),result.end());
return result;
}
};