11.29打卡-526互联

1. 从中序与后序遍历序列构造二叉树（106）

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
        private Map<Integer,Integer> map;
    private  int[] postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
         this.postorder =postorder;
         map =  new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return dfsbuild(0,inorder.length-1,0,postorder.length-1);
    }
      private TreeNode dfsbuild(int instart, int inend , int poststart,int postend) {
        if(poststart>postend||inend<instart)
            return null;
        int rootval = postorder[postend];
        int inid=map.get(rootval);
        TreeNode root = new TreeNode(rootval);
        int leftnum = inid-instart;
        root.left=dfsbuild(instart,inid-1,poststart,poststart+leftnum-1);
        root.right=dfsbuild(inid+1,inend,poststart+leftnum,postend-1);
        return root;
    }
}

2.二叉树的层序遍历 II（107）

给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
          LinkedList<List<Integer>> res =new LinkedList<>();
        if(root==null)return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
           for (int i =queue.size();i>0;i--){
                TreeNode node = queue.poll();
                list.add(node.val);
               
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
            queue.add(node.right);
            }
            res.addFirst(list);
        }
        return res;

    }
}

3. 将有序数组转成二叉搜索树(108)

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(0,nums.length-1,nums);
       
    }
    public TreeNode build(int start,int end, int[] nums){
        if(end<start)
            return null;
        int mid = (end-start)/2+start;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(start,mid-1,nums);
        root.right = build(mid+1,end,nums);
        return root;
    }
}