用有序数组构建二叉搜索树

用有序数组构建二叉搜索树

问题

这个题目说的是，给你一个递增排序的数组，你要用它构建一棵平衡的二叉搜索树。所谓平衡，是指对于这棵二叉搜索树上的每一个节点，它左右子树的高度差不能大于 1。

比如说，给你的递增数组是：

1, 2, 4, 8, 16

一种可能的构建方式是：

   4
  / \
 1   8
  \   \
   2  16

首先，这是一棵二叉搜索树。对于任意的一个节点，它左子树上的数字都小于它；右子树上的数字都大于它。

另外这棵树是平衡的，因为任何一个节点的左右子树高度差都不大于 1 。

当然，这不是唯一的构建方式。比如也可以构建成：

     4
    / \
   2   8
  /     \
 1      16

我们只需要返回任意一个平衡的二叉搜索树即可。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
    if (start > end) return null;
    int mid = start + (end - start)/2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums, start, mid-1);
    root.right = sortedArrayToBST(nums, mid+1, end);
    return root;
  }

  // Time: O(n), Space: O(log(n))
  public TreeNode sortedArrayToBSTRecursive(int[] nums) {
    if (nums == null || nums.length == 0) return null;
    return sortedArrayToBST(nums, 0, nums.length-1);
  }

  private class Item {
    TreeNode parent;
    int start, end;
    boolean isLeft;
    Item(TreeNode parent, int start, int end, boolean isLeft) {
      this.parent = parent;
      this.start = start;
      this.end = end;
      this.isLeft = isLeft;
    }
  }

  // Time: O(n), Space: O(n)
  public TreeNode sortedArrayToBSTIterative(int[] nums) {
    if (nums == null || nums.length == 0) return null;
    Stack<Item> stack = new Stack<>();
    TreeNode dummy = new TreeNode(0);
    stack.push(new Item(dummy, 0, nums.length-1, true));

    while (!stack.isEmpty()) {
      Item item = stack.pop();
      if (item.start <= item.end) {
        int mid = item.start + (item.end - item.start)/2;
        TreeNode child = new TreeNode(nums[mid]);
        if (item.isLeft) item.parent.left = child;
        else item.parent.right = child;

        stack.push(new Item(child, item.start, mid-1, true));
        stack.push(new Item(child, mid+1, item.end, false));
      }
    }
    return dummy.left;
  }

}