欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode-1382-将二叉搜索树变平衡-JavaScript

程序员文章站 2022-07-15 13:18:38
...

题目

给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。

如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。

如果有多种构造方法,请你返回任意一种。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/balance-a-binary-search-tree

示例

LeetCode-1382-将二叉搜索树变平衡-JavaScript

思路

先将二叉搜索树中序遍历,得到升序数组,再将数组构建新的平衡树即可。每次选取中间的值作为根节点。

var balanceBST = function (root) {
  let valuesLDR = [];

  /**
   * 将平衡树中序遍历为数组,此数组一定是升序的
   * @param {TreeNode} root 
   */
  function BSTtoLDR(root) {
    if (root.left) {
      BSTtoLDR(root.left);
    }
    valuesLDR.push(root.val);
    if (root.right) {
      BSTtoLDR(root.right);
    }
  }
  BSTtoLDR(root);

  /**
   * 根据升序数组构造树,每次取中间位置的值作为根节点
   * @param {Array} values 
   */
  function buildBalanceBST(values) {
    const mid = Math.floor(values.length / 2);
    const node = new TreeNode(values[mid]);
    const leftValues = values.slice(0, mid);
    if (leftValues.length) {
      node.left = buildBalanceBST(leftValues);
    }
    const rightValues = values.slice(mid + 1);
    if (rightValues.length) {
      node.right = buildBalanceBST(rightValues);
    }
    return node;
  }

  return buildBalanceBST(valuesLDR);
};

以后放在github,感觉比较好整理一点。