题目如下:
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.
给定一升序数组,要我们将其转换为平衡二叉搜索树。
二叉搜索树是这样的二叉树:
(1)左子树所有节点均小于根节点;
(2)右子树所有节点均大于根节点;
(3)左右子树的深度差不超过1;
(4)左右子树均为平衡BST。
这道题目可以通过递归解决,代码实现如下。递归函数定义为build(sortedArray,start,end),三个参数分别为题中的数组,构建平衡BST的起始下标和结束下标。递归终止条件为起始下标大于结束下标。构建平衡二叉树的过程为首先找到给定范围的中位数,作为根节点的值,然后递归求左右两棵子树。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums == null || nums.length == 0) { return null; } return build(nums, 0, nums.length - 1); } public TreeNode build(int[] nums, int start, int end) { if (start > end) { return null; } int mid = (start + end) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = build(nums, start, mid - 1); root.right = build(nums, mid + 1, end); return root; } }
- 本文固定链接: https://weiguangli.com/archives/404
- 转载请注明: lwg0452 于 Weiguang的博客 发表
捐 赠如果您觉得这篇文章有用处,请支持作者!鼓励作者写出更好更多的文章!