剑指offer18——二叉树的镜像

1. 思路——分治

def postOrder(root):
    if root == None:
    	return None
    postOrder(root.left) // left child
    postOrder(root->right);// right child
    # process root，root参数的操作过程
           

2. 代码

分治的操作步骤

① 找出基线条件，这种条件必须尽可能简单(例如涉及数组的递归问题时，基线条件一般是数组为空或只包含一个元素)

② 不断缩小问题规模(使用递归)，直到符合基线条件

本题中，我们要解决的是二叉树的镜像问题

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 1.要解决的问题：返回镜像树的根节点
    # 翻转二叉树的左右孩子，左右孩子进行相同的操作
    def traverse(self,pts):
        if pts == None:  # -----基线条件
            return None
        lval = self.traverse(pts.left) # -----递归条件，缩小了问题规模
        rval = self.traverse(pts.right)# -----递归条件，缩小了问题规模
        pts.left = rval
        pts.right = lval
        
        return pts
    def Mirror(self, root):
        # write code here
        if root == None:
            return None
        self.traverse(root)