538.把二叉搜索树转换为累加树

链接：538.把二叉搜索树转换为累加树
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

题解 1 - typescript

• 编辑时间：2020-09-21
• 执行用时：244ms
• 内存消耗：47MB
• 编程语言：typescript
• 解法介绍：中序遍历排序后利用 reduce 累加。

function convertBST(root: TreeNode | null): TreeNode | null {
  if (isNull(root)) return null;
  const arr: number[] = [];
  inorder(root);
  toGreaterTree(root);
  return root;
  function isNull(node: TreeNode | null): node is null {
    return node === null;
  }
  function toGreaterTree(node: TreeNode | null): void {
    if (isNull(node)) return;
    node.val = arr.reduce((total, cur) => total + (cur > node.val ? cur : 0), node.val);
    toGreaterTree(node.left);
    toGreaterTree(node.right);
  }
  function inorder(node: TreeNode | null): void {
    if (isNull(node)) return;
    inorder(node.left);
    arr.push(node.val);
    inorder(node.right);
  }
}