108. 将有序数组转换为二叉搜索树
LeetCode题目要求
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230126221428698-1196003548.png)
示例
输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230126221540031-185200844.png)
解题思路
要构造一个二叉树,首先要找到 root 节点,题目要求构造的是个高度平衡的二叉树,那么从有序数组中找到 mid 索引,就可以构造出二叉搜索树,且在保证二叉搜索树特性的情况下,完成节点的构造。
假设根据 nums = [-10,-3,0,5,9],5 个节点来构造,进行二分,找到 root 节点 0,同时切分为 [-10, -3] 和 [5, 9] 两个子数组,接着来构造 root 的左右子节点,先看 [-10, -3] 这个子数组是左子树,且构造要符合二叉搜索树,这是需继续二分,直到剩余一个节点,才构造;[5, 9] 作为右子树做同样的操作
上代码
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
// 左闭右开
return traversal(nums, 0, nums.length);
/**
索引 0 1 2 3 4
-10, -3, 0, 5, 9
递归,根据 nums 的 mid 索引找 root 节点,通过 nums 不断进行二分,完成左右节点构造,构造顺序为 中 左 右
0
/ \
-3 9
/ /
-10 5
*/
}
public TreeNode traversal(int[] nums, int start, int end) {
// 递归终止条件
if (end - start < 1) {
return null;
}
// 节点数等于 1 个时, 开始构造节点, 左闭右开
if (end - start == 1) {
return new TreeNode(nums[start]);
}
int mid = (start + end) / 2;
// 确定 root 节点 构造 root 节点
TreeNode root = new TreeNode(nums[mid]);
root.left = traversal(nums, start, mid);
root.right = traversal(nums, mid + 1, end);
return root;
}
}
重难点
找 root 节点,始终保持一个 左闭右开,或者左闭右闭的原则 对数组不断切分。直到剩下一个元素才构造节点。
附:学习资料链接
标签:10,nums,23,构造,Day,108,二叉,root,节点 From: https://www.cnblogs.com/blacksonny/p/17068345.html