给一个有序数组生成平衡搜索二叉树(java)

给一个有序数组生成平衡搜索二叉树

给定一个有序的数组,用这个数组生成一个平衡搜索二叉树.

这个题还是很简单的,知道什么时平衡搜索二叉树就行了,
左边值小于头节点值,头节点值小于右边值,左树右树高度差不超过1.

递归生成

解题思路.因为要生成平衡的搜索树,因此有序数组的中间值 ,
就是头节点的值,
然后左边构造成左树,
右边构造成右树.
然后这样递归就构造出一颗平衡搜索二叉树了.

先定义一个树结构

  public  class Node{public int val;public Node left;public Node right;public Node(int val) {this.val = val;}}

代码演示;

 /*** 给定一个有序数组 生成平衡搜索二叉树* @param arr* @return*/public static Node generateNode(int[]arr){if (arr == null || arr.length == 0){return null;}//递归函数时return process(arr,0,arr.length - 1);}/*** 递归函数* @param arr* @param L* @param R* @return*/public static Node process(int[]arr,int L,int R){//base caseif(L > R){return null;}//中间点int mid = L +  (R - L)/2;Node head = new Node(arr[mid]);head.left = process(arr,L,mid - 1);head.right = process(arr,mid + 1,R);return head;}

二叉树专题

二叉树的序列化和反序列化(java)

leetcode 二叉树展开为链表

镜像二叉树和求二叉树最大深度