LeetCode#101-Symmetric Tree 解题思路

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 1.6k | 阅读时长 ≈ 1 分钟

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

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

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

即检查一个二叉树是否围绕其中心对称。

解题思路

另外写一个函数 flipAndCheck()，对于两个非空且值相等的根，递归判断该根的两个子根是否与另一根的子根的翻转相等。再在主函数里再调用这个函数。解法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root is None:
            return True
        return flipAndCheck(root.left, root.right)
    	
        def flipAndCheck(root1, root2):
            # 基线条件
            if not root1 and not root2：
            	return True
            if not root1 or not root2：
            	return False
            if root1.val != root2.val:
                return False
            # 递归
            return flipAndCheck(root1.left, root2.right) and flipAndCheck(root1.right, root2.left)

感觉不好直观地理解，可以将下面这个二叉树进行验证，但也挺绕的orz：

  • 首先是判断flipAndCheck(l_2,r_2)
  • 再判断flipAndCheck(l_2.left=3, r_2.right=3) and flipAndCheck(l_2.right=4, r_2.left=4)
  • 再判断 flipAndCheck(l_2_3.left=5, r_2_3.right=5) and flipAndCheck(l_2_3.right=6, r_2_3.left=6) and flipAndCheck(l_2_4.left=6, r_2_4.right=6) and flipAndCheck(l_2_4.right=5, r_2_4.left=5)
1
2
3
4
5
6
7
         1
       /   \
     2       2
   /  \     /  \
  3    4    4   3
 / \  / \  / \  / \
5   6 6  5 5  6 6  5