leetcode226 Invert Binary Tree

 1 """
 2 Invert a binary tree.
 3 Example:
 4 Input:
 5      4
 6    /   
 7   2     7
 8  /    / 
 9 1   3 6   9
10 Output:
11      4
12    /   
13   7     2
14  /    / 
15 9   6 3   1
16 """
17 class TreeNode:
18     def __init__(self, x):
19         self.val = x
20         self.left = None
21         self.right = None
22 
23 class Solution1(object):
24     def invertTree(self, root):
25         if root == None:
26             return root
27         root.left, root.right = root.right, root.left
28         self.invertTree(root.left)
29         self.invertTree(root.right)
30         return root
31 """
32 递归都可以用栈来迭代实现
33 因此存在用栈遍历的第二种解法
34 """
35 class Solution2(object):
36     def invertTree(self, root):
37         if not root:
38             return root
39         stack = [root]
40         while stack:
41             node = stack.pop(-1)  #先弹出根结点，再依次让左右孩子压栈
42             if node.left:
43                 stack.append(node.left) #pop(0)是弹出list的头元素 pop(-1)弹出尾元素
44             if node.right:              #在这里用两个均可，即队列和栈都可以
45                 stack.append(node.right)
46             node.left, node.right = node.right, node.left
47         return root