今年的校招薪资，有点猛啊。。。|spiderlinebreak|字节|校招|示例|算法|薪资

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

25届秋招大厂正在陆续开奖，最近两天各网友也都晒出了自己的开奖薪资，今年的校招薪资和往年也有很大不同，下面截取了字节，美团，快手，百度，华为等大厂的开奖薪资，基本上普遍年薪都在40w以上。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第100题：相同的树。

问题描述

来源：LeetCode第100题

难度：简单

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例1：

输入：p = [1,2,3], q = [1,2,3] 输出：true

示例2：

输入：p = [1,2], q = [1,null,2] 输出：false

两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4

问题分析

这题让判断两棵二叉树是否相等，可以从根节点开始比较，如果根节点的值不同，这两颗二叉树肯定不相等。如果根节点的值相同，还需要判断左子树和右子树是否也相等，左右子树的判断和根节点的判断一样，所以它实际上就是个递归。

JAVA：

public boolean isSameTree(TreeNode p, TreeNode q) {
    // 如果都为空我们就认为他是相同的
    if (p == null && q == null)
        return true;
    // 如果一个为空，一个不为空，很明显不可能是相同的树，直接返回false即可
    if (p == null || q == null)
        return false;
    // 如果这两个节点都不为空并且又不相等，所以他也不可能是相同的树，直接返回false
    if (p.val != q.val)
        return false;
    // 走到这一步说明节点p和q是完全相同的，我们只需要在比较他们的左右子节点即可
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

C++：

public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        // 如果都为空我们就认为他是相同的
        if (p == nullptr && q == nullptr)
            return true;
        // 如果一个为空，一个不为空，很明显不可能是相同的树，直接返回false即可
        if (p == nullptr || q == nullptr)
            return false;
        // 如果这两个节点都不为空并且又不相等，所以他也不可能是相同的树，直接返回false
        if (p->val != q->val)
            return false;
        // 走到这一步说明节点p和q是完全相同的，我们只需要在比较他们的左右子节点即可
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }

Python：

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    # 如果都为空我们就认为它是相同的
    if not p and not q:
        return True
    # 如果一个为空，一个不为空，很明显不可能是相同的树，直接返回False即可
    if not p or not q:
        return False
    # 如果这两个节点都不为空并且又不相等，所以他也不可能是相同的树，直接返回False
    if p.val != q.val:
        return False
    # 走到这一步说明节点p和q是完全相同的，我们只需要再比较他们的左右子节点即可
    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

笔者简介

博哥，真名：王一博，毕业十多年，作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以下载我整理的1000多页的PDF算法文档。