題目
給定一個二叉樹, 按層輸出節(jié)點的值到一個二維數組.
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;
}
總結
持續(xù)優(yōu)化, 找到更優(yōu)結果. 循環(huán)往往優(yōu)于遞歸.
熟練掌握queue.
