leetcode 108. Convert Sorted Array to Binary Search Tree

2017-08-02

题意

把一个排序好的数组，构建成一个平衡二叉搜索树（balanced Binary Search Tree）,顾名思义平衡二叉树和二叉搜索树的合并。

我的思路

因为排序好的数组是已知的。考虑到平衡二叉树的特性那么根节点就应该是已知的。根据根节点划分出两个数组位置依次递归

我的代码

盲敲过不了。。还是遗忘了很多细节，比如函数参数名不能和传入参数的对象名字一样，一样的名字会导致操作的是同一个对象。

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = new TreeNode(0);
        if(nums.length>=1) travelNode(root,nums,0,nums.length-1);
        else return null;
        return root;
    }
    public void travelNode(TreeNode index,int[] nums,int start,int end){
        if(end<start) {
            index = null;
            return;
        }
        int mid = start+(end-start+2)/2-1;
        index.val = nums[mid];
        if((mid-1)>=start) {
            index.left = new TreeNode(0);
            travelNode(index.left,nums,start,mid-1);
        }
        if(end>=mid+1) {
            index.right = new TreeNode(0);
            travelNode(index.right, nums, mid + 1, end);
        }
    }
}

大神代码

和我不同的地方，是递归函数返回节点。这么做减少了在函数中去new的步骤，从而精简了代码。

public TreeNode sortedArrayToBST(int[] num) {
    if (num.length == 0) {
        return null;
    }
    TreeNode head = helper(num, 0, num.length - 1);
    return head;
}

public TreeNode helper(int[] num, int low, int high) {
    if (low > high) { // Done
        return null;
    }
    int mid = (low + high) / 2;
    TreeNode node = new TreeNode(num[mid]);
    node.left = helper(num, low, mid - 1);
    node.right = helper(num, mid + 1, high);
    return node;
}