【EASY】Convert Sorted Array to Binary Search Tree

发布于: 2019-03-05 19:45
阅读: 49
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

分析过程

  • 输入:已经排序的数组
  • 输出:根据数组生成的二叉搜索树
  • 思路:取数组中点作为根,左右递归即可。需要注意的是结果是不唯一的,题中的 case 对应两种树结构,具体见注释。

解决方法

class Solution {
public:
    
    TreeNode *_sortedArrayToBST(vector<int>& arr, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        // 以下树对应的是以下m的取法
        //     0
        //   /   \
        //  -3    5
        //  /      \
        // -10      9
        //
        // int m = left + (right - left) / 2;
        
        // 以下树对应的是以下m的取法
        //     0
        //   /   \
        //  -3    9
        //  /    /
        // -10  5
        //
        // 本质的区别是,偶数长度时,取中间靠前那个为根,还是靠后那个为根
        // 题目要求的是这一种
        int m = left + (right - left) / 2;
        
        TreeNode *root = new TreeNode(arr[m]);
        
        root->left = _sortedArrayToBST(arr, left, m - 1);
        root->right = _sortedArrayToBST(arr, m + 1, right);
        
        return root;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return _sortedArrayToBST(nums, 0, (int)nums.size() - 1);
    }
};

Thanks for reading.

All the best wishes for you! 💕