将有序数组转换为二叉搜索树

题目分析题解总结

题目

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

分析

本题提供一个有序数组，要求将其转换为一个高度平衡二叉搜索树（左右子树高度差不超过一）。 由于数组已经排序好，每个数左边的数都比本数小，右边的数都比本数大，所以选择中间的数为根节点，然后左右递归即可，这样一方面满足二叉树左节点小，右边节点大，另一方面，最后的左右子树高度差也不会超过一。

题解

public static TreeNode sortedArrayToBST(int[] nums) { int index = nums.length / 2; TreeNode root = new TreeNode(nums[index]); root.left = getNode(0,index-1,nums); // 左右递归 root.right = getNode(index+1,nums.length-1,nums); return root; } public static TreeNode getNode(int l, int r, int[] nums){ if(l>r) return null; int index = (l+r)/2; // 选取中间的数为根节点 TreeNode root = new TreeNode(nums[index]); root.left = getNode(l,index-1,nums); // 左右递归 root.right = getNode(index+1,r,nums); return root; }

总结

一道简单题，看到二叉树就想到递归，需要注意答案不唯一，血的教训！！！