题解 | 对称的二叉树

1、解题思路

1. 递归方法：对称二叉树的条件是：左子树和右子树互为镜像。两个子树互为镜像的条件： 它们的根节点值相同。左子树的左子树与右子树的右子树互为镜像。左子树的右子树与右子树的左子树互为镜像。
2. 迭代方法（BFS或DFS）：使用队列或栈进行层次遍历或深度遍历。每次比较两个节点（左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点）。如果所有节点都满足对称条件，则二叉树对称。

2、代码实现

C++（递归）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    bool isSymmetrical(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr) {
            return true;
        }
        return isMirror(pRoot->left, pRoot->right);
    }

    bool isMirror(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) {
            return true;
        }
        if (left == nullptr || right == nullptr) {
            return false;
        }
        return (left->val == right->val) && isMirror(left->left, right->right) &&
               isMirror(left->right, right->left);
    }
};

C++（迭代）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    bool isSymmetrical(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr) {
            return true;
        }

        queue<TreeNode*> q;
        q.push(pRoot->left);
        q.push(pRoot->right);

        while (!q.empty()) {
            TreeNode* left = q.front();
            q.pop();
            TreeNode* right = q.front();
            q.pop();

            if (left == nullptr && right == nullptr) {
                continue;
            }
            if (left == nullptr || right == nullptr) {
                return false;
            }
            if (left->val != right->val) {
                return false;
            }

            q.push(left->left);
            q.push(right->right);
            q.push(left->right);
            q.push(right->left);
        }

        return true;
    }
};

Java（递归）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    public boolean isSymmetrical (TreeNode pRoot) {
        // write code here
        if (pRoot == null) return true;
        return isMirror(pRoot.left, pRoot.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return (left.val == right.val) &&
               isMirror(left.left, right.right) &&
               isMirror(left.right, right.left);
    }
}

Java（迭代）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    public boolean isSymmetrical (TreeNode pRoot) {
        // write code here
        if (pRoot == null) return true;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(pRoot.left);
        q.offer(pRoot.right);

        while (!q.isEmpty()) {
            TreeNode left = q.poll();
            TreeNode right = q.poll();

            if (left == null && right == null) continue;
            if (left == null || right == null) return false;
            if (left.val != right.val) return false;

            q.offer(left.left);
            q.offer(right.right);
            q.offer(left.right);
            q.offer(right.left);
        }

        return true;
    }
}

Python（递归）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot:
            return True
        return self.isMirror(pRoot.left, pRoot.right)
    
    def isMirror(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.isMirror(left.left, right.right) and \
               self.isMirror(left.right, right.left)

Python（迭代）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
from collections import deque

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot:
            return True
        
        q = deque()
        q.append(pRoot.left)
        q.append(pRoot.right)
        
        while q:
            left = q.popleft()
            right = q.popleft()
            
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            
            q.append(left.left)
            q.append(right.right)
            q.append(left.right)
            q.append(right.left)
        
        return True

3、复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：递归方法为 O(h)（树高），迭代方法为 O(n)（队列存储节点）。