Day 15 二叉树
102. 二叉树的层序遍历
层序遍历二叉树需要借助到队列
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr) return {};
queue<TreeNode*> que;
vector<vector<int>> rst;
que.push(root);
TreeNode *cur;
while (!que.empty())
{
int len = que.size();
vector<int> level;
while (len--)
{
cur = que.front();
que.pop();
level.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
rst.push_back(level);
}
return rst;
}
};
226. 翻转二叉树
递归方法
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return root;
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
return root;
}
};
迭代方法
就是简单的用上前序遍历迭代方法实现,不用想的太复杂文章来源:https://www.toymoban.com/news/detail-524592.html
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
stack<TreeNode*> stk;
stk.push(root);
TreeNode *cur;
while (!stk.empty())
{
cur = stk.top();
stk.pop();
swap(cur->left, cur->right);
if (cur->left) stk.push(cur->left);
if (cur->right) stk.push(cur->right);
}
return root;
}
};
101. 对称二叉树
递归方法
class Solution {
bool helper(TreeNode *leftNode, TreeNode *rightNode)
{
if (leftNode == nullptr && rightNode == nullptr) return true;
if (leftNode == nullptr || rightNode == nullptr) return false;
if (leftNode->val == rightNode->val)
{
bool inSide = helper(leftNode->right, rightNode->left);
bool outSide = helper(leftNode->left, rightNode->right);
return inSide && outSide;
}
else return false;
}
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return helper(root->left, root->right);
}
};
迭代方法
这里使用了队列来存放两个要比较的结点。也可以使用栈,方法是类似的。文章来源地址https://www.toymoban.com/news/detail-524592.html
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
queue<TreeNode*> que;
que.push(root->left);
que.push(root->right);
while (!que.empty())
{
TreeNode *node1 = que.front();
que.pop();
TreeNode *node2 = que.front();
que.pop();
if (!node1 && !node2) continue;
else if (!node1 || !node2 || node1->val != node2->val) return false;
else
{
// outside
que.push(node1->left);
que.push(node2->right);
// inside
que.push(node1->right);
que.push(node2->left);
}
}
return true;
}
};
到了这里,关于算法刷题Day 15 二叉树的层序遍历+翻转二叉树+对称二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!