JZ18 二叉树镜像

题目

操作给定的二叉树，将其变换为源二叉树的镜像。

思路

• 先遍历, 节点入栈, 再依次出栈调换左右节点
• 遍历的过程中调换左右节点

代码

1# -*- coding:utf-8 -*-
2class TreeNode:
3    def __init__(self, x):
4        self.val = x
5        self.left = None
6        self.right = None
7
8# -*- coding:utf-8 -*-
9# class TreeNode:
10#     def __init__(self, x):
11#         self.val = x
12#         self.left = None
13#         self.right = None
14class Solution:
15    # 先遍历, 入栈, 再调换左右节点
16    def Mirror(self, root):
17        # 判断传入节点是否为空
18        if root is None:
19            return None
20        line_node = self.printLevelNode(root)
21        # print(line_node)
22        while line_node:
23            tmp = line_node.pop()
24            if tmp.left or tmp.right:
25                tmp.left, tmp.right = tmp.right, tmp.left
26        return tmp
27    # 层次遍历二叉树, 被调用
28    def printLevelNode(self, root):
29        line_node = []
30        res = []
31        line_node.append(root)
32        while line_node:
33            tmp = line_node.pop(0)
34            res.append(tmp)
35            if tmp.left:
36                line_node.append(tmp.left)
37            if tmp.right:
38                line_node.append(tmp.right)
39        return res
40
41    # 层次遍历的过程中调换左右节点
42    def Mirror2(self, root):
43        if root is None:
44            return None
45        line_node = []
46        line_node.append(root)
47        while line_node:
48            tmp = line_node.pop(0)
49            if tmp.left:
50                line_node.append(tmp.left)
51            if tmp.right:
52                line_node.append(tmp.right)
53            # if tmp.left or tmp.right:
54            tmp.left, tmp.right = tmp.right, tmp.left
55        return root
56
57    # 递归遍历的过程中调换左右节点
58    def Mirror3(self, root):
59        if root is None:
60            return None
61        root.left, root.right = root.right, root.left
62        self.Mirror3(root.left)
63        self.Mirror3(root.right)
64        return root
65
66
67if __name__ == '__main__':
68    node1 = TreeNode(8)
69    node2 = TreeNode(6)
70    node3 = TreeNode(10)
71    node4 = TreeNode(5)
72    node5 = TreeNode(7)
73    node6 = TreeNode(9)
74    node7 = TreeNode(11)
75    node1.left = node2
76    node1.right = node3
77    node2.left = node4
78    node2.right = node5
79    node3.left = node6
80    node3.right = node7
81    sl = Solution()
82    ls = sl.Mirror3(node1)
83    print(ls)
84    for i in sl.printLevelNode(ls):
85        print(i.val)