LeetCode，翻转二叉树

微客鸟窝

发布于 2021-08-18 15:33:29

2510

发布于 2021-08-18 15:33:29

文章被收录于专栏：Go语言指北

力扣题目：

翻转一棵二叉树。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/invert-binary-tree/

解题

递归

❝这是一道很经典的二叉树问题。我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。 ❞

递归思想，关键点是找到结束边界和递归点。题目中，我们先假设二叉树只有一个根节点，根节点有一个左孩子和一个右孩子，即：

思路就是如果根节点 root 为空，说明树不存在，直接返回 nil，否则，我们将 root 节点的左右孩子进行交换，解题可以这样写：

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    left := root.Left
    right := root.Right
    root.Left = right
    root.Right = left
    return root
}

但是二叉树不止这么简单，于是，我们就加入递归，以为 root 的左右孩子还有自己的孩子，孩子还有自己的孩子...，每个孩子可以作为根节点，可以使用使用上面的代码，递归点就是在左右孩子处，完整代码：

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    left := invertTree(root.Left) //递归点
    right := invertTree(root.Right) //递归点
    root.Left = right
    root.Right = left
    return root
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-04，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树