厦门手机网站建设公司/近期的时事热点或新闻事件

题目描述

翻转一棵二叉树。

方法一：先序dfs

解题思路

• 交换根节点的左子树和右子树
• 递归分别交换左子树的节点和右子树的节点

代码实现

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

方法二：后续dfs

解题思路

• 递归到叶子节点，交换叶子节点的左子树和右子树
• 一层一层返回，交换

代码实现

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

方法三：bfs

解题思路

• 层序遍历二叉树
• 交换该层每个节点的左子树和右子树
• 迭代交换子树的左子树和右子树

代码实现

func invertTree(root *TreeNode) *TreeNode {if root == nil {return root}queue := make([]*TreeNode, 0)queue = append(queue, root)for len(queue) > 0 {node := queue[0]queue = queue[1:]node.Left, node.Right = node.Right, node.Leftif node.Left != nil {queue = append(queue, node.Left)}if node.Right != nil {queue = append(queue, node.Right)}}return root
}