二叉搜索树
二叉搜索树可以是一颗空树或者具备如下特性的一棵树:
- 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值
- 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值
- 任意节点的左、右子树也分别为二叉搜索树
- 没有键值相等的节点
- 一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
前置条件
给定一个数组,但此数组是有序的。
解决思路
通过结合二叉搜索树的特性可以得知,二叉搜索树通过 中序遍历之后得到的是一个有序数组。
中序输出的过程为:左节点 -> 根节点 -> 右节点
此时发现其实这是一个逆向过程,根据已有的排序数组逆向构造二叉树。
那么我们如何保证高度平衡呢?
很简单,我们是否想到了二分法?通过二分法找到根节点,然后再在二分好数组的基础上重复性的执行。
想到了重复,我们根据自己的经验学习,第一反应出现的应该是递归和迭代。此种情况我们采用递归。
递归处理过程中,除了分析出递归公式之外,还要分析分析递归条件。
此场景的递归条件即为 startIndex 和 endIndex 的比较,当子数组的 startIndex > endIndex 的时候即退出递归逻辑。
具体实现
public TreeNode sortedArrayToBST(int[] nums) { /** --- 边界条件处理 ---- **/ if( nums == null || nums.length == 0) { return null; } int startIndex = 0, endIndex = nums.length - 1; /** --- TreeNode treeNode = createTree(nums, startIndex, endIndex); return treeNode; } private TreeNode createTree(int[] nums, int start, int end) { /** --- 递归条件 --- **/ if(start > end) { return null; } /** --- 此处 mid 计算是要保证 startIndex 存在一个基准值 ---- **/ int mid = start + (end-start) / 2; TreeNode root = new TreeNode(nums[mid]); /** --- startIndex 及 endIndex 不能通过事先变量定义,因为在处理递归过程中 ** 退出递归之后能够找回之前的 startIndex 及 endIndex 值,所以在参数中通过 ** 变量运算来传参保证能够找回递归之前的值 **/ root.left = createTree(nums, start, mid -1 ); root.right = createTree(nums, mid + 1, end); return root; }
知识点: 平衡二叉搜索树、递归、二分法、中序遍历