Leetcode - 构建树系列

解题中心思想

1. 确定出根节点，

2. 然后再递归的为根节点赋值左右孩子的过程。

题目特点

1. 先序 + 中序 的遍历数组

2. 中序 + 后序 的遍历数组

3. 一个有序数组 （构造结果不唯一，构造二叉搜索树）

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

详细说明

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

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

相关题目

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

   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
   };
   

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

   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
   
   };
   

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

   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)
       
   };
   

4. 有序链表转换二叉搜索树

   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)
   };