一天一大 leet(将有序数组转换为二叉搜索树)难度:简单-Day20200703

前端小书童

发布于 2020-09-24 11:37:30

1620

发布于 2020-09-24 11:37:30

文章被收录于专栏：前端小书童

题目:

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，
它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

抛砖引玉

左右两个子树高度差不超过 1：那么树的根节点应该在数组的中心位置
已经知道根节点，那下一个节点应该也是在剩余范围的中心位置
类似二分法，圈定一个范围，每次取范围的中心位置
利用递归，完成多个范围同时保留二分结果
递归终止条件：圈定的范围缩小为0

即：把数组按二分法拆分区间，再把区间拼接成树

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
    if (!nums) {
        return null;
    }

    let node = new TreeNode();

    return buildTree(nums, node);

    function buildTree(arr, node) {
      let len =  arr.length
      if (len === 0) return null;
      let mid = parseInt(len / 2, 10);
      node.val = arr[mid];

      let left = [];
      for (let i = 0; i < mid; i++) {
          left.push(arr[i]);
      }
      if (left.length > 0) {
          node.left = new TreeNode();
          buildTree(left, node.left);
      }

      let right = [];
      for (let i = mid + 1; i < arr.length; i++) {
          right.push(arr[i]);
      }
      if (right.length) {
          node.right = new TreeNode();
          buildTree(right, node.right);
      }

      return node;
    }
};

既然划分了区域和知道区域的下一个需要的树节点(中点)
那可以尝试不形成真实的数组区域，里索引在原数组中标记区域
直接利用递归完成区域内每个节点追加到树上的操作

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
  return build(nums, 0, nums.length - 1)
  function build(nums, left, right) {
      if (left > right) return null
      let mid = parseInt((left + right) / 2, 10);
      let node = new TreeNode(nums[mid])
      node.left = build(nums, left, mid - 1)
      node.right = build(nums, mid + 1, right);
      return node;
  }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-07-03，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法