LeetCode 0226.翻转二叉树

翻转二叉树

LeetCode226. 翻转二叉树

题目描述

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

思路

遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转两次。层序遍历依然可以。

这里我使用前序遍历的方式翻转二叉树。

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        // 根节点为空
        return nil
    }
    // DFS(递归)
    // 交换左右子节点
    root.Left, root.Right = root.Right, root.Left // 中
    invertTree(root.Left) // 左
    invertTree(root.Right) //右
    return root
}

Link

GitHub