【LeetCode】108. Convert Sorted Array to Binary Search Tree 解法及注释，分治法，递归

秒速五厘米 2022-07-28 11:57 125阅读 0赞

108. Convert Sorted Array to Binary Search Tree

Total Accepted: 73365 Total Submissions: 197776 Difficulty: Medium

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

【分析】

题意：给定一个升序序列，将其转化成一个平衡的二叉搜索树。有【LeetCode】98.99.101题的基础，这个题比较简单，这个题涉及到的新概念是“平衡二叉搜索树”：[**平衡二叉树**][Link 1]（Balanced Binary Tree，BBT）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、[Treap][]等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的[数列][Link 2]，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

二叉搜索树（BST）前面已经提到，其特征在于中序遍历序列为升序，本题给定的数据集正是升序，因此结合平衡二叉树的定义我们很容易构造成一个平衡二叉搜索树。步骤如下：

1、根据BST和BBT的定义，我们可采用“**分治**”的思想来解决。如果序列不为空，第一个首末下标分别为start和end，那么给定升序序列中下标为mid=(end-start)/2的数据必为根节点数值；该数据左侧\[start,mid-1\]和右侧\[mid+1,end\]升序数据同样遵循BST和BBT的定义，这两个升序序列的中间数据，即下标（mid-1-start)/2和(end-mid-1)/2对应的数据分别为左右子树的根节点。

2、图解，如升序序列\[1,2,3,5,6,7\],欲构成平衡二叉搜索树的话，中间节点5为根节点，5的左侧升序序列\[1,2,3\]中间点2为根节点，右侧升序序列\[6,7\],“中间”节点6为根节点，以此内推直到节点全部用完。如下图所示：满足BST和BBT的定义，中序遍历结果\[1,2,3,5,6,7\]

![Center][]

【解法及注释】

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) 
        {
            if(nums.size()==0)return NULL;//输入序列为空
            return establishNode(nums,0,nums.size()-1);//分治
        }
        
        TreeNode* establishNode(vector<int>& nums,int start,int end)
        {
            
            if(start<=end)
            {
              int mid=start+((end-start)>>1);//升序序列中间数据为该序列构成的平衡二叉树根结点
              TreeNode *root=new TreeNode(nums[mid]);//建立根结点
              root->left=establishNode(nums,start,mid-1);//建立左右子树
              root->right=establishNode(nums,mid+1,end);
              return root;//返回
            }
            return NULL;//当升序序列数据用完，返回NULL，即叶子节点左右子树为空
        }
    };

[Link 1]: http://baike.baidu.com/link?url=siIOC4-q2QV53wuw2GoxZF34ZlRyUsxM-j7F8G0Wv1ra19ebxBQUwrD040pDmfeTzgtFqKTTzpp4sGYN9hcbua
[Treap]: http://baike.baidu.com/view/956602.htm
[Link 2]: http://baike.baidu.com/view/39749.htm
[Center]: /images/20220724/1159a2a676e64d52a58d33b18d3a09f5.png