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

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

2024年10月，有媒体报道称字节跳动的大模型训练任务遭到实习生攻击。随后字节发文回应：确有实习生发生严重违纪，涉事实习生已于2024年8月被公司辞退，并将其行为同步给所在学校和行业联盟，交由学校处理。

打开网易新闻 查看精彩图片

拒字节跳动内部人士介绍，由于田某为在读博士，公司将其辞退后首先交由校方处理。但在事件处理期间，田某多次对外否认，称攻击模型训练任务的不是自己，而是别的实习生，甚至报警称遭到造谣。考虑到田某完全没有意识到错误，且涉事行为已触犯公司安全红线，字节跳动最终决定向法院起诉，以表明公司严肃态度、杜绝类似事件再次发生。

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

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

来看下今天的算法题，这题是LeetCode的第101题：对称二叉树。

问题描述

来源：LeetCode第101题

难度：简单

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例1：

打开网易新闻 查看精彩图片

输入：root = [1,2,2,3,4,4,3] 输出：true

示例2：

打开网易新闻 查看精彩图片

输入：root = [1,2,2,null,3,null,3] 输出：false

  • 树中节点数目在范围 [1, 1000] 内

  • -100 <= Node.val <= 100

问题分析

这题让判断二叉树是否是轴对称，如果把根节点去掉，就变成了两棵子树，这题也就变成了判断两棵子树是否对称，和我们昨天讲的 非常类似。

而判断子树是否对称， 需要左子树和右子树比较，右子树和左子树比较 ，如下图所示：

打开网易新闻 查看精彩图片

JAVA：

public boolean isSymmetric(TreeNode root) {
    if (root == null)
        return true;
    // 从两个子节点开始判断
    return helper(root.left, root.right);
}

public boolean helper(TreeNode left, TreeNode right) {
    // 如果左右子节点都为空，说明当前节点是叶子节点，返回true
    if (left == null && right == null)
        return true;
    // 如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
    if (left == null || right == null || left.val != right.val)
        return false;
    // 然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
    return helper(left.left, right.right) && helper(left.right, right.left);
}

C++：

public:
    bool isSymmetric(TreeNode *root) {
        if (root == nullptr)
            return true;
        // 从两个子节点开始判断
        return helper(root->left, root->right);
    }

    bool helper(TreeNode *left, TreeNode *right) {
        // 如果左右子节点都为空，说明当前节点是叶子节点，返回true
        if (left == nullptr && right == nullptr)
            return true;
        // 如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if (left == nullptr || right == nullptr || left->val != right->val)
            return false;
        // 然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
        return helper(left->left, right->right) && helper(left->right, right->left);
    }

Python：

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    def helper(left, right):
        # 如果左右子节点都为空，说明当前节点是叶子节点，返回true
        if left is None and right is None:
            return True
        # 如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if left is None or right is None or left.val != right.val:
            return False
        # 然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
        return helper(left.left, right.right) and helper(left.right, right.left)

    # 从两个子节点开始判断
    return helper(root.left, root.right)

笔者简介

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