By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

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

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

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

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

1.1、解题思路

根据中序遍历的特性，总是寻找中间的节点作为跟节点

1.2、算法

public TreeNode sortedArrayToBST(int[] nums) {
    return inSort(nums, 0 , nums.length-1);
}

public TreeNode inSort(int[] nums, int strat, int end) {
    //边界判断
    if (strat > end) {
        return null;
    }
    //找出排序数组的中间位置
    int index = (strat + end)/2 ;
    TreeNode node = new TreeNode(nums[index]) ;
    node.left = inSort(nums, strat, index-1);
    node.right = inSort(nums, index+ 1, end);
    return node;
}

1.3、测试


@Test
public void test(){
    int[] nums = {-10, -3, 0, 5, 9};
    TreeNode treeNode = sortedArrayToBST(nums);
    LinkedList<Integer> linkedList = new LinkedList<>();
    collect(treeNode, linkedList);
    System.out.println(linkedList);
}


public  void collect(TreeNode root, LinkedList<Integer> linkedList) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        //表示每行有多少个
        int hangSize = queue.size();
        //遍历每行的数据
        while (hangSize > 0) {
            //从队列中取出，打印根节点
            TreeNode node  = queue.remove();
            hangSize--;
            if (node == null){
                linkedList.add(null);
            }else {
                linkedList.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
        }
    }
}



public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
    TreeNode(int x, TreeNode left, TreeNode right) {
        this.val = x;
        this.left = left;
        this.right = right;

    }
}

​

ContactAuthor