Day 5/100 算法 | 有序链表转换二叉搜索树

1、题目描述:

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

Day 5/100 算法 | 有序链表转换二叉搜索树_第1张图片

2、思路

1)链表转成数组;
2)找到数组的中间节点;
3)遍历左右逐步遍历;

3、基础知识

1)位移找中间值

N>>>1就代表N的二进制右移一位,二进制右移一位就能得到中间值。
例如
10>>>1
10的二进制代码为 1010
向右移动一位后为 0101
即 5

2)二叉树定义

二叉查找树(Binary Search Tree)又叫二叉排序树(Binary Sort Tree),它是一种数据结构,支持多种动态集合操作,如 Search、Insert、Delete、Minimum 和 Maximum 等。

  • 二叉查找树要么是一棵空树,要么是一棵具有如下性质的非空二叉树:
  • 若左子树非空,则左子树上的所有结点的关键字值均小于根结点的关键字值。
  • 若右子树非空,则右子树上的所有结点的关键字值均大于根结点的关键字值。
  • 左、右子树本身也分别是一棵二叉查找树(二叉排序树)。

4、实现代码如下:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
  // 根据索引start到end的子数组构建子树
  let arr=[]
    while(head){//链表转有序数组
        arr.push(head.val)
        head=head.next
    }
    const buildBinarySearchTree=(start,end)=>{
        if(start>end){//左侧比右侧小
            return null
        } 
        const mid=(start+end) >>> 1 //找见中间的节点
        const root=new TreeNode(arr[mid]) //构建中间的根节点
        root.left=buildBinarySearchTree(start,mid-1) //递归左子树
        root.right=buildBinarySearchTree(mid+1,end) //递归右子树
        return root; 
    }
    return buildBinarySearchTree(0,arr.length-1)

};

参考链接

https://leetcode-cn.com/probl...

你可能感兴趣的