題目描述:
給定一個二叉樹,傳回其節點值自底向上的層次周遊。 (即按從葉子節點所在層到根節點所在的層,逐層從左向右周遊)
例如:
給定二叉樹 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
傳回其自底向上的層次周遊為:
[
[15,7],
[9,20],
[3]
]
算法思想:此題跟二叉樹的層次周遊思路一模一樣,隻是最後得到結果以後需要将結果翻轉一下。
/**
* 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<vector<int>> res;
void travel(TreeNode* root,int level){
if(res.size()==level){//如果是一個新層,添加一個新vector
res.push_back(vector<int>());
}
res[level].push_back(root->val);
if(root->left)travel(root->left,level+1);
if(root->right)travel(root->right,level+1);
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
if(root==NULL)
return res;
travel(root,0);
reverse(res.begin(),res.end());
return res;
}
};
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAnYldHL0FWby9mZvwFN4ETMfdHLkVGepZ2XtxSZ6l2clJ3LcV2Zh1Wa9M3clN2byBXLzN3btgHL9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsQTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5SM1cTN0QTOihTOzMzY4AjNzYzXxEjMwETMxAzLcFTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)