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


题目描述

题目:对称二叉树

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

一个二叉树是镜像对称的,当且仅当对于树中的每个节点 P 和 Q,其中 P 是左子树的一个节点且 Q 是右子树的一个节点,对于 P 的左子树中的任意节点都与 Q 的右子树中的对应节点镜像对称,反之亦然。

示例 1:

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

这棵树是对称的。

示例 2:

    1
   / \
  2   2
   \   \
   3    3

这棵树不是对称的。

注意

  • 如果你可以运用递归解决问题,那么这是一个很好的练习。
  • 题目中的树是通过节点类来定义的,每个节点包含整数值 val,以及指向其左子节点和右子节点的指针 leftright

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;
    }
}

class Solution {
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
        if ($root == null) {
            return true;
        }
        return $this->isMirror($root->left, $root->right);
    }
    
    private function isMirror($node1, $node2) {
        if ($node1 == null && $node2 == null) {
            return true;
        }
        if ($node1 == null || $node2 == null || $node1->val != $node2->val) {
            return false;
        }
        return $this->isMirror($node1->left, $node2->right) && $this->isMirror($node1->right, $node2->left);
    }
}

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):
        if not root:
            return True
        return self.isMirror(root.left, root.right)
    
    def isMirror(self, node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2 or node1.val != node2.val:
            return False
        return self.isMirror(node1.left, node2.right) and self.isMirror(node1.right, node2.left)

JavaScript 示例代码

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

var Solution = function() {};

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

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

以上三种语言的示例代码均实现了检查二叉树是否对称的功能。通过递归调用 isMirror 函数来比较左右子树是否镜像对称。

推荐面试题