题目1：102 二叉树的层序遍历
题目链接：102 二叉树的层序遍历
题意
根据二叉树的根节点root，返回其节点值的层序遍历
借助队列实现，因为队列是先进先出的逻辑，符合层序遍历一层一层遍历的思想
代码
/*** 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) {vector<vector<int>> result;queue<TreeNode*> que;if(root!=NULL){que.push(root);while(!que.empty()){vector<int> vec;//存放每一层的结果int size = que.size();while(size--){TreeNode* node = que.front();que.pop();if(node){vec.push_back(node->val);}if(node->left){que.push(node->left);}if(node->right){que.push(node->right);}}result.push_back(vec);}}return result;}
};题目2：226 翻转二叉树
题目链接：226 翻转二叉树
题意
根据二叉树的根节点root，翻转二叉树，将节点是左右孩子进行翻转
注意是节点指针做交换，而不是单个数值交换
首先确定遍历顺序：前序遍历 后序遍历比较直接，中序遍历得绕一下
递归法
递归三部曲
1）递归函数的参数和返回值
2）确定终止条件
3）确定单层递归逻辑
前序遍历
伪代码
代码
/*** 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;}
};后序遍历
伪代码
代码
/*** 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;}//单层递归逻辑,后序 左右中invertTree(root->left);invertTree(root->right);swap(root->left,root->right);return root;}
};中序遍历
伪代码
代码
/*** 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;}//单层递归逻辑,中序 左中右invertTree(root->left);swap(root->left,root->right);invertTree(root->left);return root;}
};层次遍历
将节点的左右孩子翻转一下就可以了
代码
/*** 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) {queue<TreeNode*> que;if(root!=NULL){que.push(root);}while(!que.empty()){int size = que.size();while(size--){TreeNode* node = que.front();que.pop();swap(node->left,node->right);if(node->left){que.push(node->left);}if(node->right){que.push(node->right);}}}return root;}
};迭代法
前序遍历
/*** 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) {stack<TreeNode*> st;if(root!=NULL){st.push(root);}while(!st.empty()){TreeNode* node = st.top();st.pop();swap(node->left,node->right);//中if(node->right){st.push(node->right);//左}if(node->left){st.push(node->left);//右}}return root;}
};题目3：101 对称二叉树
题目链接：101 对称二叉树
题意
根据二叉树的根节点root，检查该二叉树是否轴对称
递归法
递归三部曲
1）递归函数的参数和返回值 （同时遍历两棵树，根节点的左子树和根节点的右子树）
2）确定终止条件
3）确定单层递归的逻辑
代码
/*** 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 compare(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 outside= compare(left->left,right->right);//内侧bool inside = compare(left->right,right->left);bool result = outside && inside;return result;}bool isSymmetric(TreeNode* root) {return compare(root->left,root->right);}
};迭代法
队列
每次从队列中弹出两个元素(左子树的外侧节点与右子树的外侧节点，左子树的内侧节点与右子树的内侧节点)，比较。
代码
/*** 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 isSymmetric(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL){que.push(root->left);que.push(root->right);}while(!que.empty()){TreeNode* leftnode = que.front();que.pop();TreeNode* rightnode = que.front();que.pop();if(leftnode==NULL && rightnode==NULL) continue;//遍历到叶子节点的下一层else if(leftnode!=NULL && rightnode==NULL) return false;else if(leftnode==NULL && rightnode!=NULL) return false;else if(leftnode->val!=rightnode->val) return false;else{que.push(leftnode->left);//外侧节点que.push(rightnode->right);//外侧节点que.push(leftnode->right);//内侧节点que.push(rightnode->left);//内侧节点}}return true;}
};反例
为啥是continue 不是return true?
栈
和队列的流程一模一样，只不过是换了一个容器而已
代码
/*** 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 isSymmetric(TreeNode* root) {stack<TreeNode*> st;if(root!=NULL){st.push(root->left);st.push(root->right);}while(!st.empty()){TreeNode* rightnode = st.top();st.pop();TreeNode* leftnode = st.top();st.pop();if(rightnode==NULL && leftnode==NULL) continue;else if(rightnode==NULL && leftnode!=NULL) return false;else if(rightnode!=NULL && leftnode==NULL) return false;else if(rightnode->val!=leftnode->val) return false;else{st.push(leftnode->left);//外侧节点st.push(rightnode->right);//外侧节点st.push(leftnode->right);//内侧节点st.push(rightnode->left);//内侧节点}}return true;}
};反例
为啥是continue 不是return true?
