力扣做题记录（二叉树）

二叉树

打算先来了解二叉树基础，都是简单题，目的是熟悉代码格式和解题基础思路。

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(root==nullptr)return 0; queue<TreeNode*> Q; Q.push(root); int depth = 0; while(!Q.empty()){ int sz=Q.size(); while(sz>0){ TreeNode* node= Q.front(); Q.pop(); if(node->left)Q.push(node->left); if(node->right)Q.push(node->right); sz-=1; } depth+=1; } 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 a=true,b=true; if(p==nullptr&&q==nullptr)return true; else if(p!=nullptr&&q==nullptr)return false; else if(p==nullptr&&q!=nullptr)return false; else{ if(p->val!=q->val)return false; a=isSameTree(p->left,q->left); b=isSameTree(p->right,q->right); } if(a==false||b==false)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） queue<TreeNode*> 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(root==nullptr){ return nullptr; } TreeNode *left=invertTree(root->left); TreeNode *right=invertTree(root->right); root->left=right; root->right=left; 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) { queue<TreeNode*> tree_level; vector<int> num_level; vector<int> num_level_re; int level=1; if(root->left==nullptr&&root->right==nullptr)return true; else if(root->left!=nullptr&&root->right!=nullptr){level=1;} 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_re=num_level; reverse(num_level_re.begin(),num_level_re.end()); for(int i=0;i<num_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(level1>0){ 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); } };