本文共 935 字,大约阅读时间需要 3 分钟。
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树[3,9,20,null,null,15,7]
, 3 / \ 9 20 / \ 15 7
返回其自底向上的层次遍历为:
[ [15,7], [9,20], [3]]
看到这个结果很容易想到先进后出,然后就联想到栈了。。。
将每层用栈来存储。最后将栈清空。。
代码如下:
C++:
/** * 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) { queue q; stack >s; vector > ve; if(root==NULL) return ve; q.push(root); while (!q.empty()) { int Size=q.size(); vector v1; while (Size--) { TreeNode* t=q.front(); q.pop(); v1.push_back(t->val); if(t->left) q.push(t->left); if(t->right) q.push(t->right); } s.push(v1); } while (!s.empty()) { ve.push_back(s.top()); s.pop(); } return ve; }};
转载地址:http://xvaen.baihongyu.com/