大家好,我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位刚入职阿里近一个月的同学说才入职阿里26天,辞职报告已经在脑子里写了十几个版本了,新人landing太难了。
评论区有同学认为是阿里内部文化的问题,不会讲故事的i人在里面会特别痛苦,接到的任务一般都是关键词,需要自己去想目标、找方案、出成果,老板只会按时来要结果,然后挑战一番:为什么要做、目标是什么、核心价值是什么、哪里做得不好、有没有什么可以输出给其他团队的、能不能为别人的目标贡献一些内容。很多阿里的同学都表示赞同,说是就给几个字,让我改变世界。环境这种东西是我们无法改变的,能做得就是尽量去适应,每个公司都有缺点,度过了适应期一切都会变好的。
25届秋招已经开始了,我组织了一个秋招群,大家可以交流学习心得、面试经验,分享工作机会,有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档,以及投递入口,每天都会更新,大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招!计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传,今天我们来分享一道高频面试题「相同的树」。
题目描述
给你两棵二叉树的根节点 p
和 q
,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
举个例子:
输入:p = [1,2,3], q = [1,2,3]
输出:true
思路解析
递归可以分为两步:递归结束条件的处理和独立子问题的划分。
在这里两棵树是否相同可以划分两棵树的左子树是否相同和两棵树的右子树是否相同两个独立子问题。
只要保证两棵树的根节点的值相同且左右子树均相同,那么这两棵树就是相同的。
下面我们给出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 isSameTree(TreeNode* p, TreeNode* q) {
//函数出栈的条件
if (!p && !q) {
return true;
}
//函数出栈的条件
if (!p || !q || p->val != q->val) {
return false;
}
//子问题
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};python代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
#函数出栈的条件
if not p and not q:
return True
#函数出栈的条件
if not p or not q or p.val != q.val:
return False
#子问题
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
复杂度分析
时间复杂度: 因为需要遍历两棵树所有的节点,所以时间复杂度跟两棵树的总节点数相关。
空间复杂度: 因为使了递归,需要用到一个栈来保存函数的调用,栈的最大长度为树的高度,所以空间复杂度跟树的高度有关。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦!
https://leetcode.cn/premium/?promoChannel=ldtiger ,年度会员有效期比官网多俩月,季度会员有效期比官网多两个星期,还有专属福利,需要的读者朋友可以找我了解。
今天的分享就到这里,希望大家能有所收获!