代码随想录–二叉树部分
day14 二叉树第二天
文章目录
- 代码随想录--二叉树部分
- 一、力扣226--反转二叉树
- 二、力扣101--对称二叉树
- 三、力扣104--二叉树的最大深度
- 四、力扣111--二叉树的最小深度
一、力扣226–反转二叉树
代码随想录题目链接：代码随想录
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
递归法可以秒了
代码如下：
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr) return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
二、力扣101–对称二叉树
代码随想录题目链接：代码随想录
给你一个二叉树的根节点 root ， 检查它是否轴对称。
这道题用递归做的话，反而不太好写
因为要检查是否轴对称，所以其实迭代需要传入两颗树的root，比较两棵树是否对称
而仅在这两个root不为空且数字一样时，再进行下一步的检查
也就是递归检查左树的左节点和右树的右节点是否一样，以及左树的右节点和右树的左节点是否一样
代码如下：
class Solution {
public:
bool checkThem(TreeNode * leftN, TreeNode * rightN)
{
if(leftN != nullptr && rightN == nullptr) return false;
else if(leftN == nullptr && rightN != nullptr) return false;
else if(leftN == nullptr && rightN == nullptr) return true;
else if(leftN->val != rightN ->val) return false;
bool outside = checkThem(leftN->left, rightN->right);
bool inside = checkThem(leftN->right, rightN->left);
return outside && inside;
}
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
return checkThem(root->left, root->right);
}
};
用遍历法写就会简单的多，一层一层地把元素入队，每次出两个比较，都一样且队空就是对称，否则不对称
代码如下：
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
queue<TreeNode*> checkQue;
checkQue.push(root->left);
checkQue.push(root->right);
while(!checkQue.empty())
{
TreeNode * leftN = checkQue.front();
checkQue.pop();
TreeNode * rightN = checkQue.front();
checkQue.pop();
if(!leftN && !rightN) continue; // both nullptr
else if(!leftN && rightN) return false;
else if(leftN && !rightN) return false;
else if(leftN->val != rightN->val) return false;
checkQue.push(leftN->left);
checkQue.push(rightN->right);
checkQue.push(leftN->right);
checkQue.push(rightN->left);
}
return true;
}
};
附加题：力扣100–相同的树
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q) return true;
else if(!p && q) return false;
else if(!q && p) return false;
else if(p->val != q->val) return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
};
力扣572–另一颗树的子树，层序遍历+相同树判断
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q) return true;
else if(!p && q) return false;
else if(!q && p) return false;
else if(p->val != q->val) return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
queue<TreeNode *> que;
que.push(root);
while(!que.empty())
{
TreeNode * curr = que.front(); que.pop();
if(isSameTree(curr, subRoot)) return true;
if(curr->left) que.push(curr->left);
if(curr->right) que.push(curr->right);
}
return false;
}
};
三、力扣104–二叉树的最大深度
代码随想录题目链接：代码随想录
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
第一反应就是层序遍历，每次遍历+1即可
代码如下：
class Solution {
public:
int maxDepth(TreeNode* root) {
int depth = 0;
if(!root) return depth;
queue<TreeNode *> que;
que.push(root);
while(!que.empty())
{
int length = que.size();
depth ++;
for(int i = 0; i < length; i++)
{
TreeNode * curr = que.front(); que.pop();
if(curr->left) que.push(curr->left);
if(curr->right) que.push(curr->right);
}
}
return depth;
}
};
迭代法做也是可以的，迭代遍历左右树层数，选最大的那个，每层迭代向上返回时+1即可记录迭代层数
代码如下：
class Solution {
public:
int getDepth(TreeNode * curr)
{
if(!curr) return 0;
int leftDepth = getDepth(curr->left);
int rightDepth = getDepth(curr->right);
return 1+max(leftDepth, rightDepth);
}
int maxDepth(TreeNode* root) {
return getDepth(root);
}
};
可以简洁，但是为了方便回忆，就这么写吧
附加题：力扣559–N叉树的最大深度
class Solution {
public:
int maxDepth(Node* root) {
if(!root) return 0;
int depth = 0;
queue<Node *> que;
que.push(root);
while(!que.empty())
{
int length = que.size();
depth ++;
for(int i = 0; i < length; i ++)
{
Node * curr = que.front(); que.pop();
for(auto child : curr->children)
{
if(child) que.push(child);
}
}
}
return depth;
}
};
或
class Solution {
public:
int maxDepth(Node* root) {
if(!root) return 0;
int depth = 0;
for(auto child : root->children)
{
int curr_depth = maxDepth(child);
depth = depth > curr_depth ? depth : curr_depth;
}
return depth + 1;
}
};
四、力扣111–二叉树的最小深度
代码随想录题目链接：代码随想录
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
跟最大深度不同的是，返回时需要检查一下这个节点是否有左右树，如果是单侧树的话，不能单纯返回1+min的结果
只有该节点左右树都有或者都没有的情况下才能返回1+min，因为此时的节点才有可能是叶子节点
代码如下：
class Solution {
public:
int getDepth(TreeNode * curr)
{
if(!curr) return 0;
int leftDepth = getDepth(curr->left);
int rightDepth = getDepth(curr->right);
if(!curr->left && curr->right) return 1 + rightDepth;
if(!curr->right && curr->left) return 1 + leftDepth;
return 1 + min(leftDepth, rightDepth);
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};
迭代法：正常的层序遍历，但是在检查到第一个叶子节点的时候就return，下面的就不用遍历了
因为是一层一层的遍历，每次遍历都是同一层的叶子节点，也就无所谓是哪一个，深度是一样的
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
int depth = 0;
queue<TreeNode *> que;
que.push(root);
while(!que.empty())
{
int length = que.size();
depth ++;
for(int i = 0; i < length; i ++)
{
TreeNode * curr = que.front(); que.pop();
if(curr->left) que.push(curr->left);
if(curr->right) que.push(curr->right);
if(!curr->left && !curr->right) return depth;
}
}
return depth;
}
};
