Convert Sorted Array to Binary Search Tree问题_有序数组转换成二叉搜索树

Tue May 12 13:16:49 CST 2015 774 算法

文章摘要来自LeetCode的题目。给定一个升序排列的数组,要求生成一个平衡二叉搜索树。题目已经给出树结点的结构。

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

二叉搜索树(BST是)是一颗空树,或者它的左孩子的值比根结点小,右孩子的值比根结点大,并且它的左右子树都是二叉搜索树。

平衡二叉树(B-Tree)是一颗空树,或者左右两个子树的高度差不能超过1,并且它的两棵子树都是平衡二叉树。


关键思路:

由于数组已经有序(升序),为满足平衡二叉树的特性,这棵树的根结点应为数组中间的数,数组前半部分的数应该位于其左子树,后半部分的数应该位于其右子树中;因此可以用递归和二分算法思想来解决这一问题,每一次找出中间的数,将中间的数保存到结点中,然后从中间分成两部分,再分别对这两部分做同样的处理。

下面为问题的java语言解法

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(num.length == 0) return null;
        return build(num, 0, num.length-1);
    }
    
    public TreeNode build(int[] num, int low, int height){
        if(low <= height){
            int mid = (low+height)/2;
            TreeNode root = new TreeNode(num[mid]);
            root.left = build(num, low, mid-1);
            root.right = build(num, mid+1, height);
            return root;
        }
        else return null;
    }
}

Problem from leetcode


打赏
打赏

分享到:




Largest Number

Min Stack问题