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; } }
标签:node,11.29,right,TreeNode,val,int,打卡,left From: https://www.cnblogs.com/forever-fate/p/17865977.html