题目
给定一个二叉树, 按层输出节点的值到一个二维数组.
Input: [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output: [[3],[9,20],[15,7]]
思路1
递归, 相当于先序遍历.
效率较低, 空间复杂度较大.
vector<vector<int>> res;
void readTreeNode(TreeNode *root, int level) {
if (root == nullptr) return;
cout << root->val << " | level: " << level << endl;
if (level >= res.size()) {
res.push_back(vector<int>{});
}
res[level].push_back(root->val);
readTreeNode(root->left, level+1);
readTreeNode(root->right, level+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
readTreeNode(root, 0);
return res;
}
思路2
使用queue. 每层都将子树加到queue中, 下次输出上次加入的层的值.
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
vector<int> vec;
int size = (int)q.size();
for (int i = 0; i < size;i++) {
TreeNode *node = q.front();
q.pop();
if (node == nullptr) continue;
vec.push_back(node->val);
q.push(node->left);
q.push(node->right);
}
if (!vec.empty()) res.push_back(vec);
}
return res;
}
总结
持续优化, 找到更优结果. 循环往往优于递归.
熟练掌握queue.
