README.md

翻转二叉树

难度：简单

https://leetcode-cn.com/problems/invert-binary-tree/

题目

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

示例

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

解题

递归

/**
 * 递归
 * @desc 时间复杂度 O(N)  空间复杂度 O(N)
 * @param root
 * @returns
 */
export function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) return root
  const temp = root.left
  root.left = invertTree(root.right)
  root.right = invertTree(temp)
  return root
}

迭代

/**
 * 迭代
 * @desc 时间复杂度 O(N)  空间复杂度 O(N)
 * @param root
 * @returns
 */
export function invertTree2(root: TreeNode | null): TreeNode | null {
  if (root === null) return root

  const queue = [root]

  while (queue.length) {
    const node = queue.pop()!
    const temp = node.left
    node.left = node.right
    node.right = temp

    if (node.left) queue.unshift(node.left)
    if (node.right) queue.unshift(node.right)
  }

  return root
}