二叉树的镜像(Python实现)
题目
给定一棵二叉树,要求输出其左右翻转后二叉树的中序遍历。
例:
翻转前: 翻转后:
1 | 1
/ \ | / \
2 3 | 3 2
/ \ | / \
4 5 | 5 4
解析
两个步骤:
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。- 镜像翻转:只需要遍历二叉树,每次访问一个结点时,交换其左右孩子。
- 中序遍历。
Python实现
# -*- coding:utf-8 -*-
class Node(object):
def __init__(self, value=None, lchild=None, rchild=None):
self.value = value
self.lchild = lchild
self.rchild = rchild
def mirror(root):
"""翻转镜像"""
if not root:
return
root.lchild, root.rchild = root.rchild, root.lchild
mirror(root.lchild)
mirror(root.rchild)
def in_order_traverse(root):
"""中序遍历"""
if not root:
return
in_order_traverse(root.lchild)
print(root.value)
in_order_traverse(root.rchild)
if __name__ == '__main__':
root = Node(1, Node(2, Node(4), Node(5)), Node(3))
mirror(root) # 翻转二叉树
in_order_traverse(root) # 中序遍历
更多精彩