# 二叉树

# 遍历系列

# 二叉树的前序遍历 (opens new window)

// 递归
function pre(root: TreeNode): void {
  if(!root) return
  console.log(root.val)
  pre(root.left)
  pre(root.right)
}

// 迭代
function pre(root: TreeNode): number[] {
  if(!root) return []
  const res: number[] = []
  const stack: TreeNode = [root]
  
  while(stack.length) {
    const node = stack.pop()
    res.push(node.val)
    node.right && stack.push(node.right)
    node.left && stack.push(node.left)
  }
  
  return res
}

# 二叉树的中序遍历 (opens new window)

// 递归
function mid(root: TreeNode): void {
  if(!root) return
  mid(root.left)
  console.log(root.val)
  mid(root.right)
}

// 迭代
function mid(root: TreeNode): number[] {
  if(!root) return []
  const res: number[] = []
  const stack: TreeNode[] = [root]
  
  while(stack.length) {
    while(root) {
      stack.push(root)
      root = root.left
    }
    const node = stack.pop()
    res.push(node.val)
    root = node.right
  }
  
  return res.slice(0, res.length - 1)
}

# 二叉树的后序遍历 (opens new window)

// 递归
function post(root: TreeNode): void {
  if(!root) return
  post(root.left)
  post(root.right)
  console.log(root.val)
}

// 迭代
function post(root: TreeNode): number[] {
  if(!root) return []
  const res: number[] = []
  const stack: TreeNode[] = [root]
  while(stack.length) {
    const node = stack.pop()
    res.push(node.val)
    node.left && stack.push(node.left)
    node.right && stack.push(node.right)
  }
  
  return res.reverse()
}

# 二叉树的层序遍历 (opens new window)

function level(root: TreeNode): number[][] {
  const res: number[][] = []
  
  function recursion(node: TreeNode, level: number): void {
    if(!node) return 
    res[level] = res[level] || []
    res[level].push(node.val)
    
    recursion(node.left, level + 1)
    recursion(node.right, level + 1)
  }
  
  recursion(root, 0)
  
  return res
}

# 遍历变种

# 二叉树的锯齿形层次遍历 (opens new window)

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  const res: number[][] = [];

  function traverse(node: TreeNode | null, level: number): void {
    if (!node) return;
    res[level] = res[level] || [];
    if (level % 2 === 0) {
      res[level].push(node.val);
    } else {
      res[level].unshift(node.val);
    }
    traverse(node.left, level + 1);
    traverse(node.right, level + 1);
  }

  traverse(root, 0);

  return res;
}

# 根据已知二叉树，求出具体值

# 求二叉树的最大深度 (opens new window)

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;

  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

# 二叉搜索树中第 K 小的元素 (opens new window)

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

function kthSmallest(root: TreeNode | null, k: number): number {
  let res: number;

  function mid(node: TreeNode | null): void {
    if (!node) return;
    mid(node.left);
    if (k === 0) return;
    else {
      res = node.val;
      k--;
    }
    mid(node.right);
  }

  mid(root);

  return res;
}

# 二叉树的最近公共祖先 (opens new window)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode {
  if(!root || root === p || root === q) return root
  
  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)
  
  if(left && right) {
    return root
  }
  
  return left || right
}

# 二叉树直径 (opens new window)

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

function diameterOfBinaryTree(root: TreeNode | null): number {
  let max = 0;

  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);

    max = Math.max(max, left + right);

    return Math.max(left, right) + 1;
  }

  dfs(root);
  return max;
}

# 求根到叶子结点数字之和 (opens new window)

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

function sumNumbers(root: TreeNode | null): number {
  let ans = 0;

  function dfs(node: TreeNode | null, s: string) {
    if (!node) return;
    s = s + node.val;
    if (!node.left && !node.right) {
      ans += +s;
      return;
    }
    dfs(node.left, s);
    dfs(node.right, s);
  }

  dfs(root, "");

  return ans;
}

# 一些特殊二叉树

# 判断二叉树是否是对称二叉树 (opens new window)

给定一个二叉树，检查它是否是镜像对称的。

function isSymmetric(root: TreeNode | null): boolean {
  function recursive(left: TreeNode | null, right: TreeNode | null): boolean {
    if (!left && !right) return true;
    if (!left || !right) return false;
    return (
      left.val === right.val &&
      recursive(left.left, right.right) &&
      recursive(left.right, right.left)
    );
  }

  return recursive(root, root);
}

# 验证二叉搜索树 (opens new window)

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

function isValidBST(root: TreeNode | null): boolean {
  function recursive(
    node: TreeNode | null,
    left: number,
    right: number
  ): boolean {
    if (!node) return true;
    if (node.val <= left || node.val >= right) return false;
    return (
      recursive(node.left, left, node.val) &&
      recursive(node.right, node.val, right)
    );
  }
  return recursive(root, -Infinity, Infinity);
}

# 从前序和中序遍历序列构造二叉树 (opens new window)

根据一棵树的前序遍历与中序遍历构造二叉树。

# 思路

构造一个二叉树需要构建三个部分：root、左子树、右子树
左子树、右子树的构建又包括了：root、左子树、右子树
解题的关键点在于定位出根节点，划分出左子树、右子树，然后递归构建左右子树

# 具体做法

preorder 数组的第一项肯定是根节点 -- 因为前序遍历的顺序是根 -> 左 -> 右
由根节点，在 inorder 左->根->右中划分出左、右子树的 inorder 序列
通过 inorder 中左右子树的节点个树，在 preorder 中确定左右子树的 preorder 序列
得到左右子树的 preorder 和 inorder 序列，就能递归构建左右子树。

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const hashMap = new Map<number, number>()
  for(let i = 0; i < inorder.length; i++) {
    hashMap.set(inorder[i], i)
  }
  
  function recursive(pStart: number, pEnd: number, iStart: number, iEnd: number): TreeNode | null {
    if(pStart > pEnd) return null
    const rootVal = preorder[pStart] // 根节点的值
    const root = new TreeNode(rootVal) // 根节点
    const mid = hashMap.get(rootVal) // 根节点在 inorder 的索引
    const leftNum = mid - iStart // 左子树的节点树
    root.left = recursive(pStart + 1, pStart + leftNum, iStart, mid - 1)
    root.right = recursive(pStart + leftNum + 1, pEnd, mid + 1, iEnd)
    return root
  }
  
  return recursive(0, preorder.length - 1, 0, inorder.length - 1)
}

# 翻转二叉树 (opens new window)

翻转二叉树。

function invertTree(root: TreeNode | null): TreeNode | null {
  if(!root) return null
  const left = invertTree(root.left)
  const right = invertTree(root.right)
  
  root.left = right
  root.right = left
  
  return root
}

# 把二叉搜索树转换为累加树 (opens new window)

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

# 思路

利用反向中序遍历，右 -> 根 -> 左的顺序依次累加

function convertBST(root: TreeNode | null): TreeNode | null {
  let cur = 0;
  function recursive(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    recursive(root.right);
    root.val += cur;
    cur = root.val;
    recursive(root.left);
    return root;
  }
  return recursive(root);
}

# 合并二叉树 (opens new window)

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

function mergeTrees(t1: TreeNode | null, t2: TreeNode | null): TreeNode | null {
  if(!t1) return t2
  if(!t2) return t1
  
  t1.val = t1.val + t2.val
  t1.left = mergeTrees(t1.left, t2.left)
  t1.right = mergeTrees(t1.right, t2.right)
  
  return t1
}

# 树的子结构 (opens new window)

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

# 思路

如果两棵树一模一样，则 B 是 A 的子树
通过递归遍历 A，让 A 的子树判断是否和 B 相同

function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
  if (!A || !B) return false;
  return (
    isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
  );
}

function isSame(A: TreeNode | null, B: TreeNode | null): boolean {
  if (!B) return true;
  if (!A) return false;
  if (A.val !== B.val) return false;
  return isSame(A.left, B.left) && isSame(A.right, B.right);
}

# 二叉树的镜像 (opens new window)

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

function mirrorTree(root: TreeNode | null): TreeNode | null {
  if (!root) return root;
  const left = mirrorTree(root.left);
  const right = mirrorTree(root.right);

  root.left = right;
  root.right = left;
  return root;
}

# 平衡二叉树 (opens new window)

给定一棵二叉树，判断它是否是高度平衡的二叉树。

# 思路

比较两颗子树的高度，两边都取最大值
查看两颗子树的高度差是否为 1
如果过大于 1，将其标记为 -1（表示不是平衡二叉树），然后每次递归时判断该节点的子树是否是平衡二叉树

function isBalanced(root: TreeNode | null): boolean {
  if (!root) return true;

  function height(node: TreeNode | null): number {
    if (!node) return -1;
    return Math.max(height(node.left), height(node.right)) + 1;
  }

  return (
    Math.abs(height(root.left) - height(root.right)) < 2 &&
    isBalanced(root.left) &&
    isBalanced(root.right)
  );
}

# 求二叉树的一些路径

# 路径总和III (opens new window)

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

# 思路

算出当前节点有多少符合条件的路线
再递归遍历左右子树，查看分别有多少符合条件的路径
加起来便是总数

function pathSum(root: TreeNode | null, sum: number): number {
  if (!root) return 0; // 若节点为空，则返回0
  const curSum = findSum(root, sum); // 查看当前节点有多少符合条件的路径
  const leftSum = pathSum(root.left, sum); // 遍历左子树看看有多少符合条件的路径
  const rightSum = pathSum(root.right, sum); // 遍历右子树看看有多少符合条件的路径
  return curSum + leftSum + rightSum;
}

// 辅助函数
function findSum(node: TreeNode | null, sum: number): number {
  if (!node) return 0; // 如果节点为空，则返回0
  const flag = node.val === sum ? 1 : 0; // 如果当前节点的值刚好相等，为1
  const leftSum = findSum(node.left, sum - node.val); // 算出左子树剩余可用的值
  const rightSum = findSum(node.right, sum - node.val); // 算出右子树剩余可用的值
  return flag + leftSum + rightSum;
}

# 路径总和II (opens new window)

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

function pathSum(root: TreeNode | null, sum: number): number[][] {
  const res: number[][] = [];

  function dfs(node: TreeNode | null, sum: number, path: number[]): void {
    if (!node) return;
    path.push(node.val);
    if (!node.left && !node.right) {
      if (node.val !== sum) return;
      else res.push([...path]);
    }
    if (node.left) {
      dfs(node.left, sum - node.val, path);
      path.pop();
    }
    if (node.right) {
      dfs(node.right, sum - node.val, path);
      path.pop();
    }
  }

  dfs(root, sum, []);

  return res;
}

# 二叉树的最大路径和 (opens new window)

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

function maxPathSum(root: TreeNode | null): number {
  let res = -Infinity;

  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(dfs(node.left), 0);
    const right = Math.max(dfs(node.right), 0);
    res = Math.max(res, left + right + node.val);
    return Math.max(left, right) + node.val;
  }
  dfs(root);

  return res;
}

# 其他

# 将二叉搜索树转换为一个排序的双向链表 (opens new window)

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

class Node {
  constructor(val: number, left: Node | null, right: Node | null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function treeToDoublyList(node: Node | null): Node | null {
  if(!node) return node
  
  let head: Node | null = null
  let tail: Node | null = null
  let pre: Node | null = null
  
  function dfs(node: Node | null): void {
    if(!node) return node
    dfs(node.left)
    // 第一个节点作为头节点
    if(!pre) head = node
		// 将上一个节点的后继指针指向当前节点
    else pre.right = node
    // 将当前指针的前驱指针指向上一个节点
    node.left = pre
    // 更新上一个节点
    pre = node
    // 更新尾部节点
    tail = node
    dfs(node.right)
  }
  
  dfs(root)
  // 首尾连接
  head.left = tail
  tail.right = head
  return head
}

# 二叉树展开为链表 (opens new window)

给定一个二叉树，原地将它展开为一个单链表。

function flatten(node: TreeNode | null): void {
  function dfs(root: TreeNode | null): TreeNode | null {
    if(!root) return;
    dfs(root.left);
    dfs(root.right);
    let pre = root.left;
    if(pre) {
    	//获取左子树最右叶子节点
      while(pre.right){
      	pre = pre.right;
      }
      //将右子树放在左子树最右右子节点后面
      pre.right = root.right;
      //将新构建的左子树放在右子树上
      root.right = root.left;
      //左子树置空
      root.left = null;
    }
  }
	dfs(root);
}

← 二分法.md 动态规划之博弈问题.md →