LeetCode 102. 二叉树的层序遍历
思路:
这道题的难点在于当遍历完某一层之后，下一层的元素是上一层元素的子节点，需要记录上一层的遍历情况。这种情况可以使用队列以及一个记录每层数量的变量来解决。让每层的节点先进入队列，在弹出的时候让它的左右节点加入队列，因为此时队列中包含有两层的元素，所以用记录每层数量的变量来解决弹出的个数。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if(root!=NULL) que.push(root);
vector<vector<int>> res;
while(!que.empty())
{
int size=que.size();
vector<int> temp;
while(size--)
{
TreeNode* node=que.front();
que.pop();
temp.push_back(node->val);
if(node->left!=NULL) que.push(node->left);
if(node->right!=NULL) que.push(node->right);
}
res.push_back(temp);
}
return res;
}
};
LeetCode 226.翻转二叉树
思路：
这里的翻转是指针的翻转，不是数值的交换，所以只用对每一个小的二叉树进行左右交换就行。
代码：
(递归版)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==NULL) return root;
swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
LeetCode 101. 对称二叉树
思路：
这道题相当于是比较左子树能不能翻转成右子树，所以采用递归法比较左子树和右子树对应位置是否相互相等
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool equal(TreeNode* left,TreeNode* right)
{
if(left==NULL && right!=NULL) return false;
else if(left!=NULL && right==NULL) return false;
else if (left==NULL && right==NULL) return true;
else if(left->val!=right->val) return false;
bool in=equal(left->right,right->left);
bool out=equal(left->left,right->right);
bool result=in&out;
return result;
}
bool isSymmetric(TreeNode* root) {
bool res=equal(root->left,root->right);
return res;
}
};
