对称二叉树

题目要求

设计一个算法，用于检查一个二叉树是否关于其主轴对称。这里的“轴对称”意味着二叉树的左子树是其右子树的镜像反射。如果一个二叉树看起来与其自身的镜像相同，那么它就是轴对称的。

解题思路

要判断一个二叉树是否轴对称，我们可以采用递归的方法。具体步骤如下：

1. 基本情况：如果二叉树为空，那么它是对称的。
2. 递归步骤：如果二叉树不为空，那么我们需要比较它的左子树和右子树。
   • 首先检查左子树和右子树的根节点值是否相同。
   • 然后检查左子树的左子树与右子树的右子树是否对称，这是通过递归调用来实现的。
   • 接着检查左子树的右子树与右子树的左子树是否对称，同样通过递归调用来实现。

如果上述比较中的所有对称性检查都通过，则二叉树是轴对称的；如果任何一个检查失败，则二叉树不是轴对称的。

在实现时，我们可以定义一个辅助函数，该函数接受两个节点作为参数，并且递归地检查这两个节点的子树是否为镜像对称。这个辅助函数将被用于比较原始二叉树的左子树和右子树。

以下是辅助函数的递归逻辑：

• 如果两个节点都为空，返回true。
• 如果其中一个节点为空，另一个不为空，返回false。
• 如果两个节点的值不相同，返回false。
• 递归地比较第一个节点的左子树与第二个节点的右子树，以及第一个节点的右子树与第二个节点的左子树。

最后，调用这个辅助函数，传入二叉树的根节点的左右子节点作为参数，得到的结果即为整个二叉树是否对称的答案。

Golang 版本

package main

import "fmt"

// TreeNode is a structure for tree nodes
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// isSymmetric checks if the tree is symmetric around its center
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isMirror(root.Left, root.Right)
}

// isMirror checks if two trees are mirror images of each other
func isMirror(t1, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    return t1.Val == t2.Val && isMirror(t1.Left, t2.Right) && isMirror(t1.Right, t2.Left)
}

func main() {
    // Example usage:
    // Construct a symmetric tree and test the function
    n1 := &TreeNode{Val: 1}
    n2 := &TreeNode{Val: 2}
    n3 := &TreeNode{Val: 2}
    n4 := &TreeNode{Val: 3}
    n5 := &TreeNode{Val: 4}
    n6 := &TreeNode{Val: 4}
    n7 := &TreeNode{Val: 3}

    n1.Left = n2
    n1.Right = n3
    n2.Left = n4
    n2.Right = n5
    n3.Left = n6
    n3.Right = n7

    fmt.Println("Is the tree symmetric? ", isSymmetric(n1))
}

这段代码定义了一个TreeNode结构体，用于构建二叉树。isSymmetric函数用于检查二叉树是否对称，它调用了isMirror函数来递归地检查两个子树是否为彼此的镜像。在main函数中，我们构建了一个示例二叉树，并调用isSymmetric函数来验证它是否对称。

C++版本

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return isMirror(root->left, root->right);
    }

private:
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL && t2 == NULL) return true;
        if (t1 == NULL || t2 == NULL) return false;
        return (t1->val == t2->val) && isMirror(t1->right, t2->left) && isMirror(t1->left, t2->right);
    }
};

int main() {
    // Example usage:
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(3);

    Solution solution;
    std::cout << "Is the tree symmetric? " << (solution.isSymmetric(root) ? "Yes" : "No") << std::endl;

    // Remember to delete the allocated memory
    delete root->left->left;
    delete root->left->right;
    delete root->right->left;
    delete root->right->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

这段 C++代码定义了一个TreeNode结构体和一个Solution类。Solution类中的isSymmetric方法用于检查二叉树是否对称，它调用了私有方法isMirror来递归地检查两个子树是否为彼此的镜像。在main函数中，我们构建了一个示例二叉树，并调用isSymmetric方法来验证它是否对称。最后，我们清理了分配的内存。

Python 版本

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.isMirror(root.left, root.right)

    def isMirror(self, t1: TreeNode, t2: TreeNode) -> bool:
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val) and self.isMirror(t1.right, t2.left) and self.isMirror(t1.left, t2.right)

# Example usage:
if __name__ == "__main__":
    # Construct a symmetric tree and test the function
    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(2)
    n4 = TreeNode(3)
    n5 = TreeNode(4)
    n6 = TreeNode(4)
    n7 = TreeNode(3)

    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    n3.left = n6
    n3.right = n7

    solution = Solution()
    print("Is the tree symmetric?", solution.isSymmetric(n1))

这段 Python 代码定义了一个TreeNode类用于创建二叉树节点，以及一个Solution类，其中包含了isSymmetric方法用于检查二叉树是否对称。isSymmetric方法调用了辅助方法isMirror，后者递归地检查两个子树是否互为镜像。在if __name__ == "__main__":块中，我们构建了一个示例二叉树，并调用isSymmetric方法来验证它是否对称。

Java 版本

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

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

public class Main {
    public static void main(String[] args) {
        // Example usage:
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        Solution solution = new Solution();
        System.out.println("Is the tree symmetric? " + solution.isSymmetric(root));
    }
}

这段 Java 代码定义了一个TreeNode类用于创建二叉树节点，以及一个Solution类，其中包含了isSymmetric方法用于检查二叉树是否对称。isSymmetric方法调用了私有方法isMirror，后者递归地检查两个子树是否互为镜像。在main方法中，我们构建了一个示例二叉树，并调用isSymmetric方法来验证它是否对称。

Rust 版本

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

use std::rc::Rc;
use std::cell::RefCell;

pub struct Solution {}

impl Solution {
    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        Self::is_mirror(&root, &root)
    }

    fn is_mirror(t1: &Option<Rc<RefCell<TreeNode>>>, t2: &Option<Rc<RefCell<TreeNode>>>) -> bool {
        match (t1, t2) {
            (Some(n1), Some(n2)) => {
                let n1 = n1.borrow();
                let n2 = n2.borrow();
                n1.val == n2.val
                    && Self::is_mirror(&n1.left, &n2.right)
                    && Self::is_mirror(&n1.right, &n2.left)
            }
            (None, None) => true,
            _ => false,
        }
    }
}

fn main() {
    // Example usage:
    let n1 = Rc::new(RefCell::new(TreeNode::new(1)));
    let n2 = Rc::new(RefCell::new(TreeNode::new(2)));
    let n3 = Rc::new(RefCell::new(TreeNode::new(2)));
    let n4 = Rc::new(RefCell::new(TreeNode::new(3)));
    let n5 = Rc::new(RefCell::new(TreeNode::new(4)));
    let n6 = Rc::new(RefCell::new(TreeNode::new(4)));
    let n7 = Rc::new(RefCell::new(TreeNode::new(3)));

    n1.borrow_mut().left = Some(n2.clone());
    n1.borrow_mut().right = Some(n3.clone());
    n2.borrow_mut().left = Some(n4.clone());
    n2.borrow_mut().right = Some(n5.clone());
    n3.borrow_mut().left = Some(n6.clone());
    n3.borrow_mut().right = Some(n7.clone());

    println!("Is the tree symmetric? {}", Solution::is_symmetric(Some(n1.clone())));
}

这段 Rust 代码定义了一个TreeNode结构体用于创建二叉树节点，并使用Rc和RefCell来允许可变共享所有权。Solution结构体包含了is_symmetric函数用于检查二叉树是否对称，它调用了私有函数is_mirror来递归地检查两个子树是否互为镜像。在main函数中，我们构建了一个示例二叉树，并调用is_symmetric函数来验证它是否对称。

总结

上面给出了使用不同编程语言（包括 Golang、C++、Python、Java 和 Rust）实现的检查二叉树是否对称的解法。这些解法都采用了递归的思路，通过比较二叉树的左子树和右子树来判断是否对称。具体步骤包括：

1. 定义一个TreeNode结构体或类来表示二叉树节点。
2. 编写一个isSymmetric或is_symmetric函数来检查二叉树是否对称，该函数调用一个辅助函数isMirror或is_mirror来递归比较两个子树是否镜像对称。
3. 在主函数中构建一个示例二叉树，并调用isSymmetric或is_symmetric函数来验证是否对称。

这些解法都遵循了相似的逻辑，但在具体语法和数据结构上有所差异，适用于不同的编程语言。