LeetCode 102 二叉树的层序遍历

这题用的队列和指针遍历法。难点在于记录每层末尾位置，这就要用到两个指针，一个end指针记录末尾节点，一个endchild跟着遍历该层内子节点位置，记录下一层末尾节点位置，方便在该层节点遍历结束后将其值赋给end指针进行下一层遍历。

代码如下：

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (!root) return res;queue<TreeNode*> myque;myque.push(root);TreeNode* end = root;TreeNode* endchild = root;while (!myque.empty()) {vector<int> level;TreeNode* cur = myque.front();while (cur != end) {level.push_back(cur->val);if (cur->left) {myque.push(cur->left);endchild = cur->left;}if (cur->right) {myque.push(cur->right);endchild = cur->right;}myque.pop();cur = myque.front();}level.push_back(cur->val);res.push_back(level);if (cur->left) {myque.push(cur->left);endchild = cur->left;}if (cur->right) {myque.push(cur->right);endchild = cur->right;}end = endchild;myque.pop();}return res;}
};

但是中午发现我好像忘了队列自带的size函数了。修改后如下：

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (!root) return res;queue<TreeNode*> myque;myque.push(root);while (!myque.empty()) {vector<int> level;int num = myque.size();while (num--) {TreeNode* cur = myque.front();level.push_back(cur->val);if (cur->left) {myque.push(cur->left);}if (cur->right) {myque.push(cur->right);}myque.pop();}res.push_back(level);}return res;}
};

这样就可以直接用队列长度区分不同层了。

LeetCode 226 翻转二叉树

测试用例很简单，直接交换左右节点指针即可。采用递归法。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (!root) return root;TreeNode* tmp = root->right;root->right = root->left;root->left = tmp;invertTree(root->left);invertTree(root->right);return root;}
};

采用层序遍历法：

class Solution {
public:void myswap(TreeNode*& root) {if (!root) return;TreeNode* tmp = root->right;root->right = root->left;root->left = tmp;}TreeNode* invertTree(TreeNode* root) {if (!root) return root;queue<TreeNode*> myque;myque.push(root);while (!myque.empty()) {int num = myque.size();while (num--) {TreeNode* cur = myque.front();myswap(cur);if (cur->left) myque.push(cur->left);if (cur->right) myque.push(cur->right);myque.pop();}}return root;}
};

前序遍历，注意要用一个指针保存root指针原始位置

class Solution {
public:void myswap(TreeNode*& root) {if (!root) return;TreeNode* tmp = root->right;root->right = root->left;root->left = tmp;}TreeNode* invertTree(TreeNode* root) {if (!root) return root;stack<TreeNode*> mysta;TreeNode* store = root;while (root || !mysta.empty()) {while (root) {myswap(root);mysta.push(root);root = root->left;}root = mysta.top();root = root->right;mysta.pop();}root = store;return root;}
};

中序遍历会遇到一些麻烦的问题，因为遍历完子节点，到根节点，要是交换了根节点，那么右节点就会变子节点了。今天打卡没有要求，暂时就实现到这里，我们看下一题。

LeetCode 101 对称二叉树

递归法：

左右子节点交换判断，其实很简单

class Solution {
public:bool check(TreeNode* p, TreeNode* q) {if (!p && !q) return true;if (!p && q) return false;if (p && !q) return false;return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);}bool isSymmetric(TreeNode* root) {return check(root, root);}
};

迭代法：

用一个队列将根节点入队列两次，之后每次取出两个节点比较，需要再往下判断的话，将两个节点左右节点相反顺序放入继续比较。

class Solution {
public:bool isSymmetric(TreeNode* root) {queue<TreeNode*> myque;if (!root) return true;myque.push(root);myque.push(root);while (!myque.empty()) {TreeNode* p = myque.front();myque.pop();TreeNode* q = myque.front();myque.pop();if (!p && !q) continue;if (!p && q) return false;if (p && !q) return false;if (p->val != q->val) return false;myque.push(p->left);myque.push(q->right);myque.push(p->right);myque.push(q->left);}return true;}
};

需要注意的是!p和!q的时候是进入下一重循环而不是直接return true