Day12 | Part2
约 239 个字 152 行代码 预计阅读时间 3 分钟
需要借助队列 → 动图参考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> res;
if (root != nullptr) q.push(root);
while(!q.empty()) {
int size = q.size();
vector<int> vec;
while(size --) {
TreeNode* node = q.front(); q.pop();
vec.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(vec);
}
return res;
}
|
返回其节点值自底向上的层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> res;
if(root) q.push(root);
while(!q.empty()) {
int size = q.size();
vector<int> vec;
while(size --) {
TreeNode* node = q.front(); q.pop();
vec.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(vec);
}
reverse(res.begin(), res.end());
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | vector<int> rightSideView(TreeNode* root) {
vector<int> res;
queue<TreeNode*> q;
if(root) q.push(root);
while(!q.empty()) {
int size = q.size();
while(size --) {
TreeNode* node = q.front(); q.pop();
if (size == 0) res.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | vector<double> averageOfLevels(TreeNode* root) {
vector<double> res;
queue<TreeNode*> q;
if(root) q.push(root);
while(!q.empty()) {
int size = q.size();
double sum = 0;
for(int i = 0; i < size; i ++) { // 不可以用while(size --) size会变成-1
TreeNode* node = q.front(); q.pop();
sum += node->val;
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back( sum / size );
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
queue<Node*> q;
if(root) q.push(root);
while(!q.empty()) {
int size = q.size();
vector<int> vec;
while(size --) {
Node* node = q.front(); q.pop();
vec.push_back(node->val);
for (auto i : node->children) //孩子入队
if(i) q.push(i);
}
res.push_back(vec);
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | vector<int> largestValues(TreeNode* root) {
vector<int> res;
queue<TreeNode*> q;
if(root) q.push(root);
while(!q.empty()) {
int size = q.size(), max = INT32_MIN; // 初始最大为一个小值
while(size --) {
TreeNode* node = q.front(); q.pop();
max = (node->val > max ? node->val : max);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(max);
}
return res;
}
|
递归
| Node* connect(Node* root) {
if(!root) return nullptr;
if(root->left) root->left->next = root->right;
if(root->right && root->next) root->right->next = root->next->left;
connect(root->left), connect(root->right);
return root;
}
|
区别在于上题是完美二叉树, 此题并不是
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | Node* connect(Node* root) {
queue<Node*> q;
if(root) q.push(root), q.push(nullptr);
while(q.size() > 1) {
auto cur = q.front(); q.pop();
if(!cur) {
q.push(nullptr);
continue;
}
cur->next = q.front();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
return root;
}
|
每个节点左右孩子进行交换即可
| TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return root;
swap(root->left, root->right);
invertTree(root->left); invertTree(root->right);
return root;
}
|
也可以利用层序
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*> q;
if(root != nullptr) q.push(root);
while(!q.empty()) {
int size = q.size();
while(size --) {
TreeNode* node = q.front(); q.pop();
swap(node->left, node->right);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return root;
}
|
要比较内侧和外侧节点是否分别对应相等 → 如图
- 即左节点的左孩子与右节点的右孩子(外侧) & 左节点的右孩子与右节点的做孩子(内侧)
| bool compare(TreeNode* left, TreeNode* right) {
if (!left || !right) return left == right;
return (left->val == right->val)
&& compare(left->left, right->right)
&& compare(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return compare(root->left, root->right);
}
|
