翻转二叉树,

1.递归

当前节点不为空则交换左右子节点,递归非常直观。

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

2.循环,队列存储(BFS,非递归)

该方法类似树的层次遍历,出队元素交换左右子节点,当前节点左右不为空则入队。

func invertTree2(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    queue := []*TreeNode{root}
    for len(queue) != 0 {
        cur := queue[0]
        queue = queue[1:]
        cur.Left, cur.Right = cur.Right, cur.Left
        if cur.Left != nil {
            queue = append(queue, cur.Left)
        }
        if cur.Right != nil {
            queue = append(queue, cur.Right)
        }
    }
    return root
}

3.循环,栈存储(DFS,非递归)

其实给我的感觉和BFS差不多,只是每次取栈顶元素交换左右子节点,当前节点左右子节点不为空则入栈。

func invertTree3(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    stack := []*TreeNode{root}
    for {
        ls := len(stack) - 1
        if ls < 0 {
            break
        }
        cur := stack[ls]
        stack = stack[:ls]
        cur.Left, cur.Right = cur.Right, cur.Left
        if cur.Left != nil {
            stack = append(stack, cur.Left)
        }
        if cur.Right != nil {
            stack = append(stack, cur.Right)
        }
    }
    return root
}

captcha