个人觉得这个算法的思维很妙，需要考虑到几个地方，下面在给出代码之前，先对思想进行一个详细分析：
-
题目
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).- 按层遍历
- 每层从左到右遍历
- 返回一个二维数组
- 思路分析
- 首先返回的是二维数组，那么需要知道二维数组有多大，所有应该对这棵树使用DFS的思想获取高度
- 对于主要逻辑，按层遍历也通过DFS的思想进行，注意下是从左到右添加元素
- 代码展示
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
int getHeightUsingDFS(TreeNode *treeNode) {
if (treeNode == NULL) {
return 0;
}
int leftHeight = getHeightUsingDFS(treeNode->left);
int rightHeight = getHeightUsingDFS(treeNode->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
void soluteUsingDFS(vector<vector<int>> &vector, TreeNode *treeNode, int level) {
if (treeNode == NULL) {
return;
}
vector[level].push_back(treeNode->val);
soluteUsingDFS(vector, treeNode->left, level+1);
soluteUsingDFS(vector, treeNode->right, level+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
int height = getHeightUsingDFS(root);
vector<vector<int>> allValueInLevelOrder(height);
soluteUsingDFS(allValueInLevelOrder, root, 0);
return allValueInLevelOrder;
}
