101. 对称二叉树

题目描述

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

解题

要检查一个二叉树是否是对称的，可以编写一个递归函数来比较树的左子树和右子树是否是镜像对称的。具体步骤如下：

1. 如果树为空，那么它是对称的。
2. 如果树只有一个节点，它也是对称的。
3. 比较树的左子树和右子树：
   • 左子树的左子树应该等于右子树的右子树。
   • 左子树的右子树应该等于右子树的左子树。

我们可以用递归来实现这个比较。首先编写一个辅助函数 isMirror，用于递归比较两个子树是否镜像对称。然后在主函数 isSymmetric 中调用这个辅助函数。

完整的代码实现 as follows：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        return isMirror(root, root)
    }

    private func isMirror(_ t1: TreeNode?, _ t2: TreeNode?) -> Bool {
        if t1 == nil && t2 == nil {
            return true
        }
        if t1 == nil || t2 == nil {
            return false
        }
        return (t1?.val == t2?.val) &&
               isMirror(t1?.right, t2?.left) &&
               isMirror(t1?.left, t2?.right)
    }
}

解释

1. isSymmetric 函数检查树是否对称，它调用 isMirror 函数来比较树的左右子树。
2. isMirror 函数递归地比较两个子树是否镜像对称：
   • 如果两个子树都为空，它们是镜像对称的。
   • 如果一个子树为空，而另一个不为空，它们不是镜像对称的。
   • 如果两个子树的根节点值相等，并且一个子树的左子树与另一个子树的右子树镜像对称，同时一个子树的右子树与另一个子树的左子树镜像对称，则它们是镜像对称的。

进阶

用迭代方法解决这个问题

要使用迭代方法检查二叉树是否对称，可以利用队列（或栈）来模拟递归的过程。基本思想是将树的两个子树的节点成对地放入队列中，并且成对地比较这些节点是否对称。

迭代方法步骤

1. 如果树为空，它是对称的。
2. 使用一个队列初始化，将根节点的左右子节点成对地放入队列中。
3. 迭代地从队列中取出一对节点，检查它们是否对称：
   • 如果两个节点都是 nil，继续检查下一对节点。
   • 如果一个节点是 nil 而另一个不是，树不是对称的。
   • 如果两个节点的值不相等，树不是对称的。
4. 如果节点对称，则将它们的子节点成对地放入队列中，以便后续比较。具体来说，左节点的左子节点和右节点的右子节点成对，左节点的右子节点和右节点的左子节点成对。

实现代码 as follows：

import Foundation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        guard let root = root else {
            return true
        }
        
        var queue = [(TreeNode?, TreeNode?)]()
        queue.append((root.left, root.right))
        
        while !queue.isEmpty {
            let (left, right) = queue.removeFirst()
            
            if left == nil && right == nil {
                continue
            }
            
            if left == nil || right == nil {
                return false
            }
            
            if left?.val != right?.val {
                return false
            }
            
            queue.append((left?.left, right?.right))
            queue.append((left?.right, right?.left))
        }
        
        return true
    }
}

代码解释

1. 初始检查：首先检查根节点是否为 nil。如果是，树是对称的。
2. 初始化队列：使用一个队列来存储成对的节点。初始时，将根节点的左、右子节点成对地放入队列中。
3. 迭代检查：
   • 从队列中取出一对节点 (left, right)。
   • 如果两个节点都为 nil，继续处理下一对节点。
   • 如果一个节点为 nil 而另一个不是，树不是对称的，返回 false。
   • 如果两个节点的值不相等，树不是对称的，返回 false。
4. 加入子节点：
   • 将左节点的左子节点和右节点的右子节点成对地加入队列。
   • 将左节点的右子节点和右节点的左子节点成对地加入队列。
5. 完成检查：如果所有成对的节点都对称，则树是对称的，返回 true。