107. Binary Tree Level Order Traversal II
107.JPG
一、code
/**
* 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> > levelOrderBottom(TreeNode* root) {
int d = depth(root);
vector<vector<int> > ans(d, vector<int> {});
levelOrder(ans, root, d-1);
return ans;
}
void levelOrder(vector<vector<int> > &ans, TreeNode* node, int level)
{
if(!node) return;
ans[level].push_back(node->val); //1
levelOrder(ans, node->left, level-1); //2
levelOrder(ans, node->right, level-1); //3
}
//the depth of the tree
int depth(TreeNode* root)
{
if(!root) return 0;
return max(depth(root->left), depth(root->right)) + 1;
}
};
二、心得
- 创建一个depth维的
vector<vector>数组，倒序插入所给数组； - 函数
levelOrder()中，先判断是否为空，是则退出，否则递归调用自身； - 注意从左开始
push_back()，才能保持原有队形。
或者
- 将上述代码中的
//1 //2 //3改为：
ans[level].insert(ans[level].begin(),node->val);
levelOrder(ans, node->right, level-1);
levelOrder(ans, node->left, level-1);
- 此方法则是使用
insert()从右插入 - 所以下两行的代码顺序应倒过来
