Symmetric binary trees
Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes.
用单元测试描述为：
from python99.btree.p403 import symmetric
def test_symmetric():
assert symmetric([
1, [1, None, None], [1, None, None]
]) == True
assert symmetric([
1, [1, None, None], [1, [1, None, None], [1, None, None]]
]) == False
当二叉树的左右子树互为镜像时，则该二叉树是对穪的。至于「判断两棵树是否互为镜像」则可以使用分治法。当两棵树的左右子树互为镜像时，则该两棵树互为镜像。
举个例子，给定树A [a, [b, [c, None, None], None], None]，和树B [a, None, [b, None, [c, None, None]]]。
- 判断A的左子树
[b, [c, None, None], None]和B的右子树[b, None, [c, None, None]是否为镜像- 判断左子树
[c, None, None]和右子树[c, None, None]是否为镜像 - 判断右子树
None和左子树None是否互为镜像
- 判断左子树
- 判断A的右子树
None和B的左子树None是否互为镜像
代码实现：
def symmetric(tree):
return mirror(tree[1], tree[2])
def mirror(a, b):
if a is None and b is None:
return True
if a is None and b is not None:
return False
if a is not None and b is None:
return False
aleft = a[1]
aright = a[2]
bleft = b[1]
bright = b[2]
return mirror(aleft, bright) and mirror(aright, bleft)