力扣 226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
方案一：递归，遍历每一种可能。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
// 如果当前节点为空，则直接跳过
if root == nil {
return nil
}
// 交换左右节点元素值
root.Left, root.Right = root.Right, root.Left
// 递归左子树
invertTree(root.Left)
// 递归右子树
invertTree(root.Right)
// 返回当前节点
return root
}
- 时间复杂度：O(n)，n 为树中节点个数，因为需要遍历树中每个节点，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，n 为树中节点个数，树在最好情况下深度为 logn，最差情况下为 n，所以空间复杂度为 O(n)。