题目
翻转一棵二叉树。
示例:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题方法
递归 DFS 前中后序遍历
DFS 深度优先遍历
时间复杂度:O(n) n为二叉树节点数目
空间复杂度:O(n) n为递归的深度 平均情况下是为O(logN) 最坏情况下树成链状,所以空间复杂度为O(n)
迭代 BFS
BFS 广度优先遍历
层层扫荡,用队列临时存储遍历元素,不断迭代队列元素交换左右子树
时间空间复杂度O(n)
代码
// 递归 DFS 后序遍历
func mirrorTree(root *TreeNode) *TreeNode {
if root == nil{
return nil
}
//left := mirrorTree(root.Left)
//right := mirrorTree(root.Right)
//root.Left = right
//root.Right = left
root.Left,root.Right = mirrorTree(root.Right),mirrorTree(root.Left)
return root
}
// 递归 DFS 前序遍历
func mirrorTree2(root *TreeNode) *TreeNode {
if root == nil{
return nil
}
root.Left,root.Right = root.Right,root.Left
mirrorTree(root.Left)
mirrorTree(root.Right)
return root
}
// 递归 DFS 中序遍历
func mirrorTree3(root *TreeNode) *TreeNode {
if root == nil{
return nil
}
mirrorTree(root.Left)
root.Left,root.Right = root.Right,root.Left
// 这里的左节点已经被替换成了右节点
mirrorTree(root.Left)
return root
}
// 迭代 BFS
func mirrorTree4(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
// 队列
queue := []*TreeNode{root}
for len(queue) != 0 {
// 根节点出队
node := queue[0]
queue = queue[1:]
// 反转左右子树
node.Left, node.Right = node.Right, node.Left
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
return root
}