翻转二叉树.md

描述

翻转一棵二叉树。

示例：

输入：

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

输出：

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

题目链接：翻转二叉树

解法

因为 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 节点应该做什么，然后根据函数定义调用子节点，递归调用会让孩子做相同的事情。

参考了 手把手带你刷二叉树