LeetCode 226. 翻转二叉树

题目链接：LeetCode 226. 翻转二叉树

题意：

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路：

对于每一个节点，只需要考虑反转当前节点的左右子树即可，因此只需要考虑遍历顺序，本题中，采用前序和后序遍历都是可以的，但是中序遍历不行，
如果采用中序，会将某些节点反转两次，导致出错。下面以前序遍历的顺序为例

递归代码如下：

func invertTree(root *TreeNode) *TreeNode {
    dfs(root)
    return root
}
func dfs(root *TreeNode){
    if root == nil{
        return
    }
    root.Left,root.Right = root.Right,root.Left
    dfs(root.Left)
    dfs(root.Right)
}

迭代代码如下

func invertTree(root *TreeNode) *TreeNode {

    var stk []*TreeNode
    res:=root
    for root != nil || len(stk)!= 0{
        for root != nil {
            root.Left,root.Right = root.Right,root.Left
            stk = append(stk,root)
            root = root.Left
        }
        root = stk[len(stk)-1].Right
        stk = stk[:len(stk)-1]
    }
    return res 
}