对称的二叉树

对称的二叉树

【题目】：

实现一个函数，用来判断一颗二叉树是不是对称的。

【解题思路】：

1. 定义一个对称前序遍历：根->右->左；
2. 然后同时进行前序遍历和对称前序遍历，每遍历一个节点就进行判断。

示例代码：

#  define tree node
class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


#  create a tree
def create_tree(nums, index):
    if not nums:
        return None
    if index >= len(nums):
        return None

    root = TreeNode(nums[index])
    root.left = create_tree(nums, index * 2 + 1)
    root.right = create_tree(nums, index * 2 + 2)
    return root


#
def is_symmetrical(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False
    if root1.val != root2.val:
        return False
    return is_symmetrical(root1.left, root2.right) and is_symmetrical(root1.right, root2.left)


# test
# 1. create a symmetrical tree
root = create_tree([8, 6, 6, 5, 7, 7, 5], 0)
print("symmetrical tree:", is_symmetrical(root, root))

# 2. create a non-symmetrical tree
root = create_tree([8, 6, 9, 5, 7, 7, 5], 0)
print("non-symmetrical tree:", is_symmetrical(root, root))

运行结果：