描述

翻转一棵二叉树。

示例:

输入:

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

输出:

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

题目链接:翻转二叉树open in 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;
  }
}
1
2
3
4
5
6
7
8
9
10
11

递归

翻转,其实就是 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;
}
1
2
3
4
5
6
7
8
9

复杂度分析

假设树上一共 n 个节点。

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

总结

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

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

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

参考了 手把手带你刷二叉树open in new window

上次更新: 8/13/2022, 9:55:10 AM
Contributors: 九旬