python-024-镜像二叉树

---

给定一颗二叉树，编写算法将其镜像。

---

例如昨天的二叉树：

3

镜像后：

镜像

每个节点都是交换左右节点，可以用递归，对每一个节点都做同样的操作。 交换左右孩子有点像a、b交换值得方法：
tmp = a
a = b
b = tmp

这样可以防止数据丢失，交换节点也是如此。

# 从此之后函数命名都应该用下划线分割单词
def reverse_tree(root):
    # 将所有节点的左右节点交换
    if root is None:
        return
    reverse_tree(root.left_child)
    reverse_tree(root.right_child)
    #交换另个值
    tmp=root.left_child
    root.left_child = root.right_child
    root.right_child=tmp

利用递归，全部代码如下：

import random
class BiTNode:
    def __init__(self, arg):
        self.data = arg
        self.left_child = None
        self.right_child = None

# 构造二叉树
def constructBitree(x):
    # x为二叉树节点个数
    arr=[]
    for i in range(x):
        arr.append(i)
    root=arrayToBiTree(arr)
    return root
def arrayToBiTree(array):
    #判断arr是否为空
    if len(array)==0:
        return BiTNode(array[0])
    mid=len(array)//2 # 有序数组的中间元素的下标
    # print(mid)
    # start=0 # 数组第一个元素的下标
    # end=-1 # 数组最后一个元素的下标
    root = None
    if len(array) > 0:
        # 将中间元素作为二叉树的根
        root=BiTNode(array[mid])
        # 如果左边的元素个数不为零，则递归调用函数，生成左子树
        if len(array[:mid]) > 0:
            root.left_child = arrayToBiTree(array[:mid])
        # 如果右边的元素个数不为零，则递归调用函数，生成左子树
        if len(array[mid+1:]) > 0:
            root.right_child = arrayToBiTree(array[mid+1:])
    return root

# 从此之后函数命名都应该用下划线分割单词
def reverse_tree(root):
    # 将所有节点的左右节点交换
    if root is None:
        return
    reverse_tree(root.left_child)
    reverse_tree(root.right_child)
    #交换另个值
    tmp=root.left_child
    root.left_child = root.right_child
    root.right_child=tmp

#前序遍历
def print_tree_pre_order(root):
    #先判断二叉树是否为空
    #if root.left_child is None and root.right_child is None:
    if root is None:
        return root
    #先根
    print(root.data)
    #再左
    if root.left_child is not None:
        print_tree_pre_order(root.left_child)
    #再右
    if root.right_child is not None:
        print_tree_pre_order(root.right_child)

if __name__ == '__main__':
    root1 = constructBitree(10)
    print_tree_pre_order(root1)
    print("\n")
    reverse_tree(root1)
    print_tree_pre_order(root1)

运行结果：两个都是前序遍历，二叉树用的是昨天的有序数组构造二叉树的构造方法。

运行结果

今天有点水，最近学的东西。。。怎么说呢，太散了，还在学习崔庆才的爬虫开发实践，很好的一本书，等我看完后，会去看剑指offer，时间紧迫，但还是得一步一步来，一口吃不成胖子，当然还是瘦子好看一点。
至于一些python性能方面的东西我会慢慢跟上的，学的太快，每天不能花太多的时间放在简书这一块，现在还不是时候。
加油！