当前位置: 面试刷题>> 对称二叉树 (经典算法题500道)


题目描述补充

题目:对称二叉树

给定一个二叉树,检查它是否是镜像对称的(也称为对称二叉树)。

一个二叉树是镜像对称的,如果它满足以下条件:

  • 它的左子树和右子树在结构上镜像对称。
  • 相应的节点具有相同的值。

换句话说,对于树中的任意节点 PQ,如果 PQ 的左子节点,那么 P 的右子节点应该与 Q 的左子节点镜像对称,并且 P 的左子节点应该与 Q 的右子节点镜像对称。

示例 1:

    1
   / \
  2   2
 / \ / \
3  4 4  3

这棵树是对称的。

示例 2:

    1
   / \
  2   2
   \   \
   3    3

这棵树不是对称的。

PHP 代码示例

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function isSymmetric($root) {
    if ($root === null) {
        return true;
    }
    return isMirror($root->left, $root->right);
}

function isMirror($node1, $node2) {
    if ($node1 === null && $node2 === null) {
        return true;
    }
    if ($node1 === null || $node2 === null || $node1->val !== $node2->val) {
        return false;
    }
    return isMirror($node1->left, $node2->right) && isMirror($node1->right, $node2->left);
}

// 示例用法
$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);

var_dump(isSymmetric($root)); // 输出 bool(true)

Python 代码示例

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

def isSymmetric(root):
    if not root:
        return True
    return isMirror(root.left, root.right)

def isMirror(node1, node2):
    if not node1 and not node2:
        return True
    if not node1 or not node2 or node1.val != node2.val:
        return False
    return isMirror(node1.left, node2.right) and isMirror(node1.right, node2.left)

# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)

print(isSymmetric(root))  # 输出 True

JavaScript 代码示例

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function isSymmetric(root) {
    if (!root) return true;
    return isMirror(root.left, root.right);
}

function isMirror(node1, node2) {
    if (!node1 && !node2) return true;
    if (!node1 || !node2 || node1.val !== node2.val) return false;
    return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}

// 示例用法
const 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);

console.log(isSymmetric(root)); // 输出 true

码小课:在算法和数据结构的学习中,理解对称二叉树的概念及其解法是非常重要的。通过实践编写代码,可以帮助你更深入地理解递归和树结构的遍历。码小课网站中还有更多相关内容分享给大家学习,涵盖了从基础到进阶的各种算法和数据结构知识,欢迎大家访问学习。

推荐面试题