郑州网站推广公司地址,wordpress搭建子网站,运营策划,凡科网站后台在哪里.二叉树
打算先来了解二叉树基础#xff0c;都是简单题#xff0c;目的是熟悉代码格式和解题基础思路。
1、二叉树最大深度
二叉树最大深度
方法一、深度搜索
直接用原函数做递归#xff0c;比较简单
/*** Definition for a binary tree node.* struct TreeNode {* …二叉树
打算先来了解二叉树基础都是简单题目的是熟悉代码格式和解题基础思路。
1、二叉树最大深度
二叉树最大深度
方法一、深度搜索
直接用原函数做递归比较简单
/*** 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:int maxDepth(TreeNode* root) {if(root nullptr)return 0;return max(maxDepth(root-left), maxDepth(root-right))1;}
};方法二、广度搜索
利用queue来存储每一层的节点每层次循环是当前queue的长度用一个数来记录一般是2的次方然后再将新的数放置queue末尾。
class Solution {
public:int maxDepth(TreeNode* root) {if(rootnullptr)return 0;queueTreeNode* Q;Q.push(root);int depth 0;while(!Q.empty()){int szQ.size();while(sz0){TreeNode* node Q.front();Q.pop();if(node-left)Q.push(node-left);if(node-right)Q.push(node-right);sz-1;}depth1;}return depth;}
};2、相同的树
相同的树 方法一、前序遍历比较
这是自己写的思路是确定可以用递归这个是深度搜索 然后先判断节点存在再判断是否正确
/*** 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 isSameTree(TreeNode* p, TreeNode* q) {bool atrue,btrue;if(pnullptrqnullptr)return true;else if(p!nullptrqnullptr)return false;else if(pnullptrq!nullptr)return false;else{if(p-val!q-val)return false;aisSameTree(p-left,q-left);bisSameTree(p-right,q-right);}if(afalse||bfalse)return false;else return true;}
};方法二、广度搜索
来自官方题解中的一种有点复杂。
class Solution {
public: // 检查两棵二叉树是否相同 bool isSameTree(TreeNode* p, TreeNode* q) { // 如果两棵树都为空返回 true if (p nullptr q nullptr) { return true; } // 如果一棵树为空而另一棵树不为空返回 false else if (p nullptr || q nullptr) { return false; } // 创建两个队列用于广度优先搜索BFS queueTreeNode* queue1, queue2; queue1.push(p); // 将第一个树的根节点入队 queue2.push(q); // 将第二个树的根节点入队 // 当两个队列都不为空时继续比较 while (!queue1.empty() !queue2.empty()) { // 取出两个队列的前端节点进行比较 auto node1 queue1.front(); queue1.pop(); auto node2 queue2.front(); queue2.pop(); // 比较两个节点的值 if (node1-val ! node2-val) { return false; // 值不相同则树不相同 } // 获取当前节点的左右子节点 auto left1 node1-left, right1 node1-right; auto left2 node2-left, right2 node2-right; // 检查左右子节点是否存在不一致 if ((left1 nullptr) ^ (left2 nullptr)) { return false; // 只有一棵树有左子节点 } if ((right1 nullptr) ^ (right2 nullptr)) { return false; // 只有一棵树有右子节点 } // 如果左右子节点存在则将其加入队列中 if (left1 ! nullptr) { queue1.push(left1); // 将第一个树的左子节点添加到队列 } if (right1 ! nullptr) { queue1.push(right1); // 将第一个树的右子节点添加到队列 } if (left2 ! nullptr) { queue2.push(left2); // 将第二个树的左子节点添加到队列 } if (right2 ! nullptr) { queue2.push(right2); // 将第二个树的右子节点添加到队列 } } // 返回两个队列是否都为空即两棵树的结构是否相同 return queue1.empty() queue2.empty(); }
};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(rootnullptr){return nullptr;}TreeNode *leftinvertTree(root-left);TreeNode *rightinvertTree(root-right);root-leftright;root-rightleft;return root;}
};4、对称二叉树
101.对称二叉树
方法一、广度匹配
也就是迭代求解下面是我自己写的复杂的代码因为本能觉得可以把每一层存储为一个vector然后再综合比较。但是实现起来略显复杂
/*** 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* tree_level;vectorint num_level;vectorint num_level_re;int level1;if(root-leftnullptrroot-rightnullptr)return true;else if(root-left!nullptrroot-right!nullptr){level1;}else return false;tree_level.push(root-left);num_level.push_back(root-left-val);tree_level.push(root-right);num_level.push_back(root-right-val);while(tree_level.size()!0){num_level_renum_level;reverse(num_level_re.begin(),num_level_re.end());for(int i0;inum_level.size();i){if(num_level[i]num_level_re[i])continue;else return false;}num_level.clear();num_level_re.clear();// 把每层都节点和元素加入int level1 tree_level.size();while(level10){TreeNode* root_now;root_now tree_level.front();tree_level.pop();if(root_now-left!nullptr){tree_level.push(root_now-left);num_level.push_back(root_now-left-val);}else num_level.push_back(-1);if(root_now-right!nullptr){tree_level.push(root_now-right);num_level.push_back(root_now-right-val);}else num_level.push_back(-1);level1--;}// 判断每层不能为奇数if(tree_level.size()%2!0)return false; level;}return true;}
};方法二、精简迭代法
其思路是特地写一个辅助函数可以同时输入左右子树这样更加方便做迭代
class Solution {
public:bool check(TreeNode *u, TreeNode *v) {queue TreeNode* q;q.push(u); q.push(v);while (!q.empty()) {u q.front(); q.pop();v q.front(); q.pop();if (!u !v) continue;if ((!u || !v) || (u-val ! v-val)) return false;q.push(u-left); q.push(v-right);q.push(u-right); q.push(v-left);}return true;}bool isSymmetric(TreeNode* root) {return check(root, root);}
};
方法三、递归法
比较难想到下面是解释 也需要辅助函数 然后最左的和最右的分别组成对对比
class Solution {
public:// 辅助函数检查两个子树是否对称bool check(TreeNode *leftNode, TreeNode *rightNode) {// 情况 1两个节点都为空if (leftNode nullptr rightNode nullptr) {return true; // 空节点是对称的}// 情况 2其中一个节点为空另一个不为空if (leftNode nullptr || rightNode nullptr) {return false; // 不对称}// 情况 3两个节点的值不相等if (leftNode-val ! rightNode-val) {return false; // 不对称}// 递归检查// 1. 左子树的左节点和右子树的右节点是否对称// 2. 左子树的右节点和右子树的左节点是否对称bool isOuterSymetric check(leftNode-left, rightNode-right); // 检查外层bool isInnerSymetric check(leftNode-right, rightNode-left); // 检查内层// 只有外层和内层都对称整个树才对称return isOuterSymetric isInnerSymetric;}// 主函数判断二叉树是否对称bool isSymmetric(TreeNode* root) {// 如果根节点为空直接返回 true空树是对称的if (root nullptr) {return true;}// 检查左子树和右子树是否对称return check(root-left, root-right);}
};
