題目描述

Invert a binary tree.
**注：返回tree的鏡像樹

思路1

用recursive的方法，先判斷if (root)
然后交換其左右兩個(gè)node的位置
并在將該方法延伸到其左右兩個(gè)node

思路2

不用recursive的方法，用一個(gè)stack存還沒有完成swap的node
每次pop出來(lái)一個(gè)node，并swap其左右兩個(gè)node，并分別push到stack中

#Recursive Solution
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if (root):
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            self.invertTree(root.right)
        return root