Leetcode - 构建树系列

解题中心思想

确定出根节点，
然后再递归的为根节点赋值左右孩子的过程。

题目特点

先序 + 中序的遍历数组
中序 + 后序的遍历数组
一个有序数组（构造结果不唯一，构造二叉搜索树）
一个有序链表（构造结果不唯一，构造二叉搜索树，比3多了一步：遍历链表，保存为有序数组）

详细说明

对于前两个题目：先序数组、后序数组可以确定出根元素；然后利用中序划分左右孩子的范围，递归的构建整个二叉树。

对于后两者题目：二叉搜索树是left < root, root< right; 因此纳有序列表的中间元素为根，划分，递归的寻找每一个左右孩子

相关题目

从前序与中序遍历序列构造二叉树

var buildTree = function(preorder, inorder) {
    if(preorder.length <= 0) {
        return null
    }
    let root = {
        val: preorder[0]
    }

    for(let i=0; i<inorder.length; i++){
        if(inorder[i] === preorder[0]) {
            root.left = buildTree(preorder.slice(1, i+1), inorder.slice(0,i))
            root.right = buildTree(preorder.slice(i+1), inorder.slice(i+1))
        }
    }
    return root
};

从中序与后序遍历序列构造二叉树

var buildTree = function(inorder, postorder) {
    if(postorder.length==0) return null
    var len = postorder.length
    var rootVal = postorder[len-1]
    var root={
        val:rootVal
    }
    for(var i=0; i<len; i++){
        if(inorder[i]==rootVal){
            root.left = buildTree(inorder.slice(0,i),postorder.slice(0,i))
            root.right = buildTree(inorder.slice(i+1),postorder.slice(i,-1))
        }
    }
    return root

};

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

var sortedArrayToBST = function(nums) {
    // 可以转化为根据 中序遍历序列 生成二叉树
    function helper(left, right){
        if(left > right){
            return null
        }
        let mid =parseInt((left + right) / 2)
        let root = new TreeNode(nums[mid])
        root.left = helper(left, mid-1)
        root.right = helper(mid+1, right)  
        return root
    }
    return helper(0, nums.length-1)
    
};

有序链表转换二叉搜索树

var sortedListToBST = function(head) {
    let res = []
    while(head){
        res.push(head.val)
        head = head.next
    }
    let len = res.length
    function helper(left, right){
        if(left > right){
            return null
        } 
        let mid = parseInt((left + right)/2)
        let root = {
            val: res[mid]
        }
        root.left = helper(left, mid-1)
        root.right = helper(mid+1, right)
        return root
    }
    return helper(0, len-1)
};

最后编辑于：2020.02.15 16:32:50