判断二叉树是否对称

2. 描述

给定一棵二叉树,判断其是否是自身的镜像(即:是否对称) 例如:下面这棵二叉树是对称的 1 / \ 2 2 / \ / \ 3 4 4 3 下面这棵二叉树不对称。 1 / \ 2 2 \ \ 3 3 备注: 希望你可以用递归和迭代两种方法解决这个问题

示例1

输入:

{1,2,2}

复制返回值:

true

3.思路

see notes in Coding

Time: O(n) since we need to go through every pair of nodes to check if they have same values. Then go back to parent node to search another pair of nodes

Space: O(height of tree)

4. Coding

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

#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isSymmetric(self , root ):
        # write code here
        # idea
        # 1. recursion
        #  input: two nodes
        #  output: boolean
        # if two nodes' values are equal, use recursion to
        # compare node1.left, node2.right,   node1.right and node2.left
        # if not equal or one of two nodes is None but the other is not->return False
        #
        if not root:
            return True
        return self.checknodes(root.left, root.right)
    def checknodes(self, n1, n2):
        if not n1 and not n2:
            return True
        if (n1 and not n2) or (n2 and not n1):
            return False
        if n1.val != n2.val:
            return False
        return self.checknodes(n1.left, n2.right) and self.checknodes(n2.left, n1.right)
        
        

Last updated

Was this helpful?