108.将有序数组转换为二叉搜索树.md

LeetCode 108. 将有序数组转换为二叉搜索树

描述

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

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

示例:

给定有序数组: [-10,-3,0,5,9],

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

      0
     / \
   -3   9
   /   /
 -10  5

解一 [递归]

思路

每个根节点为这个有序数组的中点

1. 出口：起始索引大于或等于结束索引时 即整个数组遍历完毕 与二分查找类似
2. 使当前节点值为中点
3. 递归left与right

代码

var sortedArrayToBST = function(nums, start = 0, end = nums.length) {
    if(start >= end) return null;
    let mid = (start + end) >>> 1;
    let root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums,start,mid);
    root.right = sortedArrayToBST(nums,mid+1,end);
    return root;
};

解二 [迭代]

思路

使用栈相对递归较为复杂 其中主要问题与怎么给父级的子树赋值 只能在栈中存储父节点已经一个type来表示当前节点为左或右节点

1. 判断特殊情况 nums为空 返回null
2. 入栈参数：start, end , parent, type 起始索引、结束索引、父级节点、当前节点类型（左或右）
3. 当 start >= end 跳出当次循环 即 当前节点已无子节点
4. 每次循环入栈左子树与右子树

代码

var sortedArrayToBST = function(nums) {
  if(!nums.length) return null;
  let stack = [[0, nums.length]], root = null; // 初始栈：开始索引、结束索引  根节点为null
  while(stack.length) {
      let [start,end, parent, type] = stack.pop();
      if(start >= end){ // 最后一个节点 跳出
          continue;
      }
      let mid = (start + end) >>> 1; // 取中点 
      let newNode = new TreeNode(nums[mid]);
      // 此次两个判断可优化
      root = root || newNode;
      if(parent){
          parent[type] = newNode;
      }
      stack.push([start,mid, newNode,'left']); // 入栈左子树
      stack.push([mid+1, end, newNode,'right']); // 入栈右子树
  }
  return root;
};

// 效率优化版 把初始根节点提到循环外先创建 避免循环判断
var sortedArrayToBST = function(nums) {
  if(!nums.length) return null;
  let start = 0, end = nums.length;
  let mid = (start + end) >>> 1;
  let root = new TreeNode(nums[(0+nums.length)>>>1]);
  let stack = [[start,mid, root, 'left'],[mid+1, end, root,'right']];
  while(stack.length) {
      let [start,end, parent, type] = stack.pop();
      if(start >= end){
          continue;
      }
      mid = (start + end) >>> 1;
      let newNode = new TreeNode(nums[mid]);
      parent[type] = newNode;
      stack.push([start,mid, newNode, 'left']);
      stack.push([mid+1, end, newNode, 'right']);
  }
  return root;
};