[Leetcode][python]Symmetric Tree/对称二叉树

朴灿烈づ我的快乐病毒、 2022-06-12 07:23 88阅读 0赞

## 题目大意 ##

判断一个树是否左右对称

## 解题思路 ##

### 非递归解法 ###

按层遍历，每一层检查一下是否对称。

### 递归解法 ###

其中左子树和右子树对称的条件：  
两个节点值相等，或者都为空  
左节点的左子树和右节点的右子树对称  
左节点的右子树和右节点的左子树对称

## 代码 ##

### 递归（清晰易懂版） ###

class Solution(object):
        def judge(self, p, q):
            if p == None and q == None: 
                return True
            if p and q and p.val == q.val: # 如果一边有一边没有那么直接返回False
                return self.judge(p.left, q.right) and self.judge(p.right, q.left)
            return False
    
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            if root:
                return self.judge(root.left, root.right)
            return True

### 递归（超简洁版） ###

运算速度慢

class Solution(object):
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            def isSym(L,R):
                if L and R and L.val == R.val: 
                    return isSym(L.left, R.right) and isSym(L.right, R.left)
                return L == R
            return isSym(root, root)

### 迭代 ###

换成数组进行判断，运算速度只超过0.5%的人

class Solution(object):
        def isSymmetric(self, root):
            queue = [root]
            while queue:
                values = [i.val if i else None for i in queue]
                if values != values[::-1]: return False
                queue = [child for i in queue if i for child in (i.left, i.right)]
            return True

## 总结 ##

### 递归与迭代的关系 ###

1） 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。  
2） 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出.

### 函数嵌套 ###

python允许函数嵌套，也就是说我们可以在函数内部定义一个函数，这些函数都遵循各自的作用域和生命周期规则。