C++实现LeetCode(108.将有序数组转为二叉搜索树)

[LeetCode] 108.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 everynode 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 

这道题是要将有序数组转为二叉搜索树，所谓二叉搜索树，是一种始终满足左<根<右的特性，如果将二叉搜索树按中序遍历的话，得到的就是一个有序数组了。那么反过来，我们可以得知，根节点应该是有序数组的中间点，从中间点分开为左右两个有序数组，在分别找出其中间点作为原中间点的左右两个子节点，这不就是是二分查找法的核心思想么。所以这道题考的就是二分查找法，代码如下：

解法一：

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0 , (int)nums.size() - 1);
    }
    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int mid = left + (right - left) / 2;
        TreeNode *cur = new TreeNode(nums[mid]);
        cur->left = helper(nums, left, mid - 1);
        cur->right = helper(nums, mid + 1, right);
        return cur;
    }
};

我们也可以不使用额外的递归函数，而是在原函数中完成递归，由于原函数的参数是一个数组，所以当把输入数组的中间数字取出来后，需要把所有两端的数组组成一个新的数组，并且分别调用递归函数，并且连到新创建的cur结点的左右子结点上面，参见代码如下：

解法二：

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return NULL;
        int mid = nums.size() / 2;
        TreeNode *cur = new TreeNode(nums[mid]);
        vector<int> left(nums.begin(), nums.begin() + mid), right(nums.begin() + mid + 1, nums.end());
        cur->left = sortedArrayToBST(left);
        cur->right = sortedArrayToBST(right);
        return cur;
    }
};

类似题目：

Convert Sorted List to Binary Search Tree

参考资料：

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35220/My-Accepted-Java-Solution

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35394/6-lines-Java-Accepted-Solution

到此这篇关于C++实现LeetCode(108.将有序数组转为二叉搜索树)的文章就介绍到这了,更多相关C++实现将有序数组转为二叉搜索树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(145.二叉树的后序遍历)

    [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},    1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you d

  • C++实现LeetCode(98.验证二叉搜索树)

    [LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The ri

  • C++实现LeetCode(102.二叉树层序遍历)

    [LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7},     3 / \ 9  20 /  \ 15 

  • C++实现LeetCode(100.判断相同树)

    [LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input:     1     

  • C++实现LeetCode(101.判断对称树)

    [LeetCode] 101.Symmetric Tree 判断对称树 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric:     1 / \ 2   2 / \   / \ 3  4 4  3 But the following is not:     1 / \ 2  

  • C++实现LeetCode(107.二叉树层序遍历之二)

    C++实现LeetCode(107.二叉树层序遍历之二)

    [LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二 Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: Input: root = [3

  • C++实现LeetCode(99.复原二叉搜索树)

    [LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2]    1 / 3 \ 2 Output: [3,1,null,null,2]    3 / 1

  • C++实现LeetCode(103.二叉树的之字形层序遍历)

    [LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example

  • C++实现LeetCode(108.将有序数组转为二叉搜索树)

    [LeetCode] 108.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 wh

  • C++实现LeetCode(109.将有序链表转为二叉搜索树)

    [LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list 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

  • 前端算法leetcode109题解有序链表转换二叉搜索树

    前端算法leetcode109题解有序链表转换二叉搜索树

    目录 题目 解题思路-基础 代码实现 解题思路-优化 代码实现 解题思路-进阶 代码实现 题目 题目地址 给定一个单链表的头节点  head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树. 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1. 示例 1: 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树.

  • 剑指Offer之Java算法习题精讲字符串操作与数组及二叉搜索树

    剑指Offer之Java算法习题精讲字符串操作与数组及二叉搜索树

    题目一  解法 class Solution { public String reverseOnlyLetters(String s) { char[] chars = s.toCharArray(); int left = 0; int right = chars.length-1; while(left<=right){ char tmp = 0; if(chars[left]>='a'&&chars[left]<='z'||(chars[left]>='A'&

  • C++实现LeetCode(173.二叉搜索树迭代器)

    [LeetCode] 173.Binary Search Tree Iterator 二叉搜索树迭代器 Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and

  • C++实现LeetCode(两个有序数组的中位数)

    [LeetCode] 4. Median of Two Sorted Arrays 两个有序数组的中位数 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and 

  • C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)

    [LeetCode] 34. Find First and Last Position of Element in Sorted Array 在有序数组中查找元素的第一个和最后一个位置 Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity

  • C++实现LeetCode(95.独一无二的二叉搜索树之二)

    [LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二 Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3],

随机推荐