LeetCode 101: 对称二叉树 Symmetric Tree

爱写bug

发布于 2020-02-18 15:05:53

3150

发布于 2020-02-18 15:05:53

文章被收录于专栏：爱写Bug爱写Bug

题目：

给定一个二叉树，检查它是否是镜像对称的。

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

But the following [1,2,2,null,3,null,3] is not:

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

Note: Bonus points if you could solve it both recursively and iteratively.

解题思路：

很简单的题, 深度优先的话同时遍历二叉树的左右子结点稍加判断即可; 广度优先的话, 一次按镜像对称从两边遍历二叉树, 一次同时取出来两个结点稍加判断即可. 这里列举两种最好的解法, 复杂度相同

深度优先递归解法：

Java：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) // 根结点为空直接返回 真
            return true;
        return isSymmetricHelper(root.left, root.right); // 辅助函数传入根结点的左右子结点
    }

    private boolean isSymmetricHelper(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) // 两结点均为空时也满足镜像对称的条件, 返回为真
            return true;
        if (node1 == null || node2 == null) // 两结点只有一个为空, 则不满足对称条件, 返回值为假
            return false;
        // 当两结点值相等, 所有子结点均满足对称条件时, 返回为真, 否则返回为假
        return (node1.val == node2.val) && isSymmetricHelper(node1.left, node2.right) && isSymmetricHelper(node1.right, node2.left);
    }
}

Python:

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: # 根结点为空直接返回 真
            return True
        return self.isSymmetricHelper(root.left, root.right) # 辅助函数传入根结点的左右子结点

    def isSymmetricHelper(self, node1: TreeNode, node2: TreeNode) -> bool:
        if not node1 and not node2: # 两结点均为空时也满足镜像对称的条件, 返回为真
            return True
        if not node1 or not node2: # 两结点只有一个为空, 则不满足对称条件, 返回值为假
            return False
        # 当两结点值相等, 所有子结点均满足对称条件时, 返回为真, 否则返回为假
        return node1.val == node2.val and self.isSymmetricHelper(node1.left, node2.right) and self.isSymmetricHelper(node1.right, node2.left)

广度优先迭代解法:

Java:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) // 根结点为空直接返回 真
            return true;
        Queue<TreeNode> queue = new LinkedList<>(); // 维护一个队列, 从左右子结点同时入队维护
        queue.add(root.left);
        queue.add(root.right);
        int size;
        TreeNode node1, node2;
        while (!queue.isEmpty()) {
            node1 = queue.poll();
            node2 = queue.poll();
            if (node1 == null && node2 == null) // 两结点均为空时也满足镜像对称的条件, 跳过该层循环
                continue;
            if (node1 == null || node2 == null) // 两结点只有一个为空, 则不满足对称条件, 返回值为假
                return false;
            if (node1.val != node2.val) // 两结点值不相等时, 返回为假
                return false;
            // 按镜像对称条件, 依次入队
            queue.add(node1.left);
            queue.add(node2.right);
            queue.add(node1.right);
            queue.add(node2.left);
        }
        return true;
    }
}

Python:

class Solution:
    def isSymmetric(self, root):
        if not root: #  根结点为空直接返回 真
            return True
        queue = collections.deque() # 维护一个队列, 从左右子结点同时入队维护
        queue.append(root.left)
        queue.append(root.right)
        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()
            if node1 == None and node2 == None: # 两结点均为空时也满足镜像对称的条件, 跳过该层循环
                continue
            if node1 == None or node2 == None: # 两结点只有一个为空, 则不满足对称条件, 返回值为假
                return False
            if node1.val != node2.val: # 两结点值不相等时, 返回为假
                return False
            # 按镜像对称条件, 依次入队
            queue.append(node1.left)
            queue.append(node2.right)
            queue.append(node1.right)
            queue.append(node2.left)
        return True

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-02-10，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树