判断对称二叉树的递归与迭代方法详解 | 二叉树对称性判断

对称二叉树是指一棵二叉树的左右子树在结构上是对称的，并且对应的节点值也相同。判断一棵二叉树是否是对称二叉树，通常可以通过递归或迭代的方法来实现。

递归方法

递归方法的核心思想是定义一个辅助函数，该函数接收两个节点作为参数，分别代表左子树和右子树的根节点。然后递归地比较这两个节点的值以及它们的子树是否对称。

function isSymmetric(root) {
    if (!root) return true; // 空树是对称的
    return isMirror(root.left, root.right);
}

function isMirror(left, right) {
    if (!left && !right) return true; // 两个节点都为空
    if (!left || !right) return false; // 一个节点为空，另一个不为空
    return (left.val === right.val) && // 节点值相等
           isMirror(left.left, right.right) && // 左子树的左节点与右子树的右节点比较
           isMirror(left.right, right.left); // 左子树的右节点与右子树的左节点比较
}

迭代方法

迭代方法通常使用队列或栈来实现。我们可以将树的左右子树的根节点依次入队，然后每次从队列中取出两个节点进行比较。

function isSymmetric(root) {
    if (!root) return true;
    const queue = [];
    queue.push(root.left);
    queue.push(root.right);

    while (queue.length > 0) {
        const left = queue.shift();
        const right = queue.shift();

        if (!left && !right) continue; // 两个节点都为空
        if (!left || !right) return false; // 一个节点为空，另一个不为空
        if (left.val !== right.val) return false; // 节点值不相等

        // 将左子树的左节点与右子树的右节点入队
        queue.push(left.left);
        queue.push(right.right);

        // 将左子树的右节点与右子树的左节点入队
        queue.push(left.right);
        queue.push(right.left);
    }

    return true;
}

复杂度分析

• 时间复杂度: 无论是递归还是迭代方法，我们都需要遍历树的所有节点，因此时间复杂度为 O(n)，其中 n 是树中节点的数量。
• 空间复杂度: 递归方法的空间复杂度取决于递归栈的深度，最坏情况下为 O(n)。迭代方法的空间复杂度取决于队列的大小，最坏情况下也为 O(n)。

总结

判断一棵二叉树是否是对称二叉树，可以通过递归或迭代的方法来实现。递归方法代码简洁，但可能会受到递归深度的限制；迭代方法则通过显式地使用队列或栈来避免递归带来的栈溢出问题。根据具体场景选择合适的方法即可。