乐趣区

关于javascript:Day-5100-算法-有序链表转换二叉搜索树

jiezi

1、题目形容：

给定一个单链表，其中的元素按升序排序，将其转换为高度均衡的二叉搜寻树。
本题中，一个高度均衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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…

退出移动版