leetcode 108. Convert Sorted Array to Binary Search Tre 详细分析和递归参数确定

淡淡的烟草味﹌ 2022-07-19 02:17 63阅读 0赞

###  ###

## 108. Convert Sorted Array to Binary Search Tree ##

*  Total Submissions: 218920
 *  Difficulty: Medium

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

## 分析： ##

递归算法的参数确定很关键，可以用以下方法确定： 如果子问题的结果与原问题无关，此时使用简单的值传递即可；否则，如果原问题的变量因为子问题的调用发生了改变，此时选择引用型参数。

关于建立二叉树的算法，分解的过程一致。只是建立二叉树时候，原问题是整个二叉树，子问题是建立除了根节点之外的的左子树B.left 和右子树 B.right。并且建立好的节点和根节点之间，是需要传力根的左右子域的，即建立左右子树的BT.left 和 BT.right。因此此类问题中应该将二叉树的根节点设为参数，针对这个问题而言，应该将数组本身设为参数。而且每次子问题的数组范围也是变化的，因此需要设定数组的范围作为递归参数，即 传入数组进行递归的左右范围。

有个讲解递归参数的文章，可以看一下 ，叫 **递归算法的参数设置** http://www.docin.com/p-751177702.html

## 此题解法： ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    public class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            if(nums.length==0)return null;
            return buildBST(nums,0,nums.length-1); //注意传入递归参数的确定
        }
        
        public TreeNode buildBST(int[]nums,int left,int right){
        if(left>right)return null;
        int mid = (left+right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left=buildBST(nums,left,mid-1);
        root.right=buildBST(nums,mid+1,right);
        return root;
    }
    }

#     #