# 描述

翻转一棵二叉树。

示例:

输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

题目链接:翻转二叉树 (opens new window)

# 解法

因为 JS 没有二叉树的数据结构,所以新建了一个 TreeNode 的 Class,发现用 TS 写真香...

//Definition for a binary tree node.
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

# 递归

翻转,其实就是 Node 的左右互换。

function sortTreeNode(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;
  let temLeft = root.left;
  root.left = root.right;
  root.right = temLeft;
  sortTreeNode(root.left);
  sortTeeeNode(root.right);
  return root;
}

复杂度分析

假设树上一共 n 个节点。

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

# 总结

  • 写递归算法的总结,关键是要明确函数的[定义]是什么,然后相信这个定义,利用这个定义来推导最终结果,绝不要跳入递归的细节中。

  • 不在在意递归的细节,毕竟,人的脑袋才能压几个栈啊??

  • 写树相关的算法那,简单来说就是,先搞清楚当前 root 节点应该做什么,然后根据函数定义调用子节点,递归调用会让孩子做相同的事情。

参考了 手把手带你刷二叉树 (opens new window)

上次更新: 4/22/2021, 4:44:09 PM