给一个有序数组生成平衡搜索二叉树
- 给一个有序数组生成平衡搜索二叉树
- 递归生成
- 二叉树专题
给一个有序数组生成平衡搜索二叉树
给定一个有序的数组,用这个数组生成一个平衡搜索二叉树.
这个题还是很简单的,知道什么时平衡搜索二叉树就行了,
左边值小于头节点值,头节点值小于右边值,左树右树高度差不超过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 二叉树展开为链表
镜像二叉树和求二叉树最大深度