网站基础建设巴巴商友圈,wordpress搜索代码,微网站建设公司,黄冈网站制作题目1#xff1a;102 二叉树的层序遍历
题目链接#xff1a;102 二叉树的层序遍历
题意
根据二叉树的根节点root#xff0c;返回其节点值的层序遍历
借助队列实现#xff0c;因为队列是先进先出的逻辑#xff0c;符合层序遍历一层一层遍历的思想 代码
/*** Definitio…题目1102 二叉树的层序遍历
题目链接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:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result;queueTreeNode* que;if(root!NULL){que.push(root);while(!que.empty()){vectorint 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;}
};
题目2226 翻转二叉树
题目链接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(rootNULL){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(rootNULL){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(rootNULL){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) {queueTreeNode* 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) {stackTreeNode* 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;}
};
题目3101 对称二叉树
题目链接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 rightNULL) return false;else if(leftNULL right!NULL) return false;else if(leftNULL rightNULL) 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) {queueTreeNode* 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(leftnodeNULL rightnodeNULL) continue;//遍历到叶子节点的下一层else if(leftnode!NULL rightnodeNULL) return false;else if(leftnodeNULL 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) {stackTreeNode* 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(rightnodeNULL leftnodeNULL) continue;else if(rightnodeNULL leftnode!NULL) return false;else if(rightnode!NULL leftnodeNULL) 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?
