题目：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/solution/dfs-by-7qqqqqqq/ 思路一：广度优先搜索 利用队列，从头开始遍历 ，将节点从头开始保存数组 ，反转输出即可
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> vec; queue<TreeNode*>que; vector<int>A; if(root==NULL) return vec; que.push(root); while(!que.empty()) { int len=que.size(); for(int i=0;i<len;i++) { TreeNode* node=que.front(); que.pop(); A.push_back(node->val); if(node->left)que.push(node->left); if(node->right)que.push(node->right); } vec.push_back(A); A.clear(); } reverse(vec.begin(),vec.end()); return vec; } };思路二： 深度优先搜索
首先计算树的高度depth然后在vector开depth个vector从树根开始遍历，因为要从树底层开始输出，所以要存的答案depth-1开始存.（因为先遍历树根节点，所以数组从后往前存） 写法一： /** * 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> > ans; vector<vector<int>> levelOrderBottom(TreeNode* root) { int ma=getHeight(root); ans.resize(ma); dfs(root,--ma); return ans; } int getHeight(TreeNode* root ){ if(root==NULL) return 0; return max(getHeight(root->left),getHeight(root->right))+1; } void dfs(TreeNode* root,int dep){ if(root==NULL) return ; ans[dep].push_back(root->val); if(root->left!=NULL) dfs(root->left,dep-1); if(root->right!=NULL) dfs(root->right,dep-1); } }; 写法二： int depth(TreeNode*root) { if (root == NULL) return 0; return max(depth(root->left), depth(root->right)) + 1; } void dfs(vector<vector<int>>&res, int n, TreeNode* root) { if (root == NULL) return; res[n].push_back(root->val); if(root->left)dfs(res, n - 1, root->left); if(root->right)dfs(res, n - 1, root->right); } vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>>res; if (root == NULL) return res; int n = depth(root); res.resize(n); res[--n].push_back(root->val); if (root->left) dfs(res,n-1, root->left); if (root->right) dfs(res, n-1, root->right); return res; }