剑指18-二叉树的镜像

Posted on | In |

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
输入描述:
二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

破坏了原二叉树

用递归。

1
2
3
4
5
6
def Mirror(root):
    if root != None:
        root.left,root.right = root.right,root.left
        Mirror(root.left)
        Mirror(root.right)
    return root

不用递归。

  • 重要的是循环体有对父子关系的描述，即node.left, node.right = node.right, node.left。
  • 用队列或者栈，都行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if root is None:
            return None
        myqueue = [root]
        while len(myqueue) > 0:
            node = myqueue.pop(0)
            node.left, node.right = node.right, node.left
            if node.left:
                myqueue.append(node.left)
            if node.right:
                myqueue.append(node.right)
        return root

不破坏原二叉树，返回新建的二叉树

  • 递归。
1
2
3
4
5
6
7
8
def copyTreeMirror(root):
    if root is None:
        return root 
    rootC = TreeNode(root.val)
    rootC.left, rootC.right = copyTreeMirror(root.right), copyTreeMirror(root.left)
    
    return rootC