Binary Tree Level Order Traversa

个人觉得这个算法的思维很妙，需要考虑到几个地方，下面在给出代码之前，先对思想进行一个详细分析：

• 题目
  Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
  1. 按层遍历
  2. 每层从左到右遍历
  3. 返回一个二维数组
• 思路分析

1. 首先返回的是二维数组，那么需要知道二维数组有多大，所有应该对这棵树使用DFS的思想获取高度
2. 对于主要逻辑，按层遍历也通过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;
}