来源:编程网事
大家好,我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位脉友发帖说,工作一年多,最近写了个bug没人发现,发布到生产环境,导致生产环境挂掉了,感觉工作保不住了,很担心被干掉。
评论区的脉友针对bug发布到生产环境是谁的责任展开了讨论,大部分脉友认为开发只负责写代码,bug没测出来导致发布事故是测试的责任。还有一些脉友认为开发和测试应该共同担责。一位在字节工作的脉友说,在字节这种事情开发全责。遇到这种事情大家觉得责任应该怎样划分呢?
25届秋招已经开始了,我组织了一个秋招群,大家可以交流学习心得、面试经验,分享工作机会,有啥问题也可以在群里咨询。在群里我整理了近百家已经启动秋招企业的文档,以及投递入口,每天都会更新,大家只要按照这个文档海投就可以了。
言归正传,今天我们来分享一道高频面试原题「对称二叉树」。
给你一个二叉树的根节点 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));
}
};
# 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))
特别声明:以上内容仅代表作者本人的观点或立场,不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的,请于上述内容发布后的30天内进行。
400-690-0000 欢迎批评指正
All Rights Reserved 新浪公司 版权所有