專欄：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算法文檔 。