大家好,我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位脉友发帖说,工作一年多,最近写了个bug没人发现,发布到生产环境,导致生产环境挂掉了,感觉工作保不住了,很担心被干掉。
评论区的脉友针对bug发布到生产环境是谁的责任展开了讨论,大部分脉友认为开发只负责写代码,bug没测出来导致发布事故是测试的责任。还有一些脉友认为开发和测试应该共同担责。一位在字节工作的脉友说,在字节这种事情开发全责。遇到这种事情大家觉得责任应该怎样划分呢?
最近虎哥利用业余时间在B站讲算法,id「华南溜达虎」,我已经把算法面试高频题目列表blind75中的题目讲了一遍,力扣hot100也快讲完了,一个视频五分钟左右,利用空闲时间就把算法学会了,对跳槽找工作升职加薪甚至对考研都有帮助,感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深,清晰明了,下面是一小部分评论截图。
言归正传,今天我们来分享一道高频面试原题「对称二叉树」。
题目描述
给你一个二叉树的根节点 root , 检查它是否轴对称。
举个例子:
输入:root = [1,2,2,3,4,4,3]
输出:true
思路解析
如果做过「LeetCode 100. 相同的树」和「LeetCode 226. 翻转二叉树」这两道题,你可以先复制一棵树,把它做一次翻转,然后将翻转后的二叉树跟原来的树比较,判读是否为相同的树,如果是就说明这棵二叉树是一棵对称二叉树。但是这种方法需要先复制一棵树,遍历三次二叉树,时间复杂度和空间复杂度都不太好。
观察对称二叉树的特点,我们可以先比较 左子树的根节点和右子树的根节点是否相等,然后递归的去比较左子树的左孩子节点 和 右子树的右孩子节点是否相等,左子树的右孩子节点 和 右子树的左孩子节点是否相等。这里递归结束的边界条件就是参与比较的两个节点均为空节点或者其中一个为空节点。
下面我们给出c++和python的两种代码实现。
c++代码
/**
* 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) {
return dfs(root->left, root->right);
}
bool dfs(TreeNode* left, TreeNode* right) {
//两颗树均为空
if (!left and !right)
return true;
//其中一棵树不为空
if (!left || !right)
return false;
//递归的比较
return ((left->val == right->val) &&
dfs(left->left, right->right) &&
dfs(left->right, right->left));
}
};
python代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
return self.dfs(root.left, root.right)
def dfs(self, left, right):
# 两颗树均为空
if not left and not right:
return True
# 其中一棵树不为空
if not left or not right:
return False
# 递归的比较
return (left.val == right.val and
self.dfs(left.left, right.right) and
self.dfs(left.right, right.left))
复杂度分析
时间复杂度: 需要遍历整棵树,所以时间复杂度和树的总节点数相关。
空间复杂度: 因为使用了递归,递归的深度跟树的高度有关,所以空间复杂度和树的高度相关。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦!
https://leetcode.cn/premium/?promoChannel=ldtiger ,年度会员有效期比官网多俩月,季度会员有效期比官网多两个星期,还有专属福利,需要的读者朋友可以找我了解。
今天的分享就到这里,希望大家能有所收获!