Cracking Coding Interview - 4.2 Minimal Tree

Minimal Tree: Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

Hints: #19, #73, #116

解法1

二叉查找树具有以下特性：

任意node的左边 <= 它
任意node的右边 >= 它
它不是完全二叉树，也不是满二叉树，更不是完美二叉树

具有最小高度的tree要么是完全二叉树，要么是完美二叉树。但是完美二叉树要求节点数量必须是 2^k - 1，k=层数。因为给的数组的数量未必正好，所以应该向完全二叉树靠拢。

完全二叉树的特性是：

除了最后一层，其他层都是满的
最后一层要么是满的，要么从左到右填，能填多少就是多少。

比如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


  2
 / \
1   3

    3
   / \
  2   4
 /
1

    4
   / \
  2   5
 / \
1   3

     4
   /   \
  2     6
 / \   /
1   3 5

     4
   /   \
  2     6
 / \   / \
1   3 5   7

       5
     /   \
    3     7
   / \   / \
  2   4 6   8
 /
1

但是这个太难了，很难发现构建完全二叉搜索树的规律。

解法2

根据提示，一个最小高度的树具有这么一个特性：左边节点的数量和右边节点的数量相同。那么怎么构建呢？

当我们构建一颗子树的时候要尽量保证左右两边都有节点，如果我们对下面这个数组构建树，从左到右的顺序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


1 2 3 4 5 6 7
先用2构建子树：
  2
 / \
1   3
然后再拿4构建子树：
  4
 / \
2   6
再拿6构建子树：
  6
   \
    7
组合起来就是；
      4
    /   \
   2     6
  / \   / \
 1   3 5   7

发现规律：

每个子树都是从第2、4、6。。。个开始的，这是为了尽量保证左右都有节点。
根节点选哪个呢？当然应该选中间的元素作为根咯。

那么问题就可以变成：

选一个数组的中间元素作为根节点
对左半部分构建树，加入其左节点
对右半部分构建树，加入其右节点
左右部分的构建方法重复1-3步

所以可以看出这就是一个递归的过程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// 取下标在[start, end]区间内的元素构建树
public Node minimalTree(int[] array, int start, int end) {
  if (start > end) {
    return null;
  }
  int mid = (start + end) / 2;
  Node root = new Node(array[mid]);
  root.left = minimalTree(array, start, mid - 1);
  root.right = minimalTree(array, mid + 1, end);
  return root;
}

Cracking Coding Interview - 4.2 Minimal Tree

解法1

解法2

版权

评论

Cracking Coding Interview - 4.2 Minimal Tree

解法1

解法2

版权

相关文章

评论