本文共 4872 字，大约阅读时间需要 16 分钟。

package 计算机程序算法分类.二叉树问题;import 牛客网练习题.Solution;/** * @Classname 有序数组转变二叉搜索树108 * @Description TODO * @Date 2021/4/30 14:09 * @Created by xjl */public class 有序数组转变二叉搜索树108 {    public class TreeNode {        int val;        TreeNode left;        TreeNode right;        public TreeNode(int val) {            this.val = val;        }    }    public TreeNode sortedArrayToBST(int[] nums) {        return helper(nums, 0, nums.length - 1);    }    public TreeNode helper(int[] nums, int left, int right) {        if (left > right) {            return null;        }        // 总是选择中间位置左边的数字作为根节点        int mid = (left + right) / 2;        TreeNode root = new TreeNode(nums[mid]);        root.left = helper(nums, left, mid - 1);        root.right = helper(nums, mid + 1, right);        return root;    }    public TreeNode sortedArrayToBSTTest(int[] nums) {        return buidtree(nums, 0, nums.length - 1);    }    private TreeNode buidtree(int[] nums, int left, int right) {        if (left > right) {            return null;        }        int mid = left + (right - left) / 2;        TreeNode node = new TreeNode(nums[mid]);        node.left = buidtree(nums, left, mid - 1);        node.right = buidtree(nums, mid + 1, right);        return node;    }}

package 计算机程序算法分类.dfs深度优先广度优先问题;import java.util.HashMap;import java.util.Map;/** * @Classname 前中序数组构造二叉树  这里是的没有的重复的数字 * @Description TODO * @Date 2021/4/12 15:50 * @Created by xjl */public class 前中序数组构造二叉树 {    public class TreeNode {        int val;        TreeNode left;        TreeNode right;        public TreeNode(int val) {            this.val = val;        }    }    public TreeNode buildTree(int[] preorder, int[] inorder) {        int preLen = preorder.length;        int inLen = inorder.length;        if (preLen != inLen) {            throw new RuntimeException("Incorrect input data.");        }        //存储中序遍历的值        Map
   
     map = new HashMap<>();        for (int i = 0; i < inLen; i++) {            map.put(inorder[i], i);        }        return buildTreedfs(preorder, 0, preLen - 1, map, 0, inLen - 1);    }    private TreeNode buildTreedfs(int[] preorder, int preLeft, int preRight, Map
    
      map, int inLeft, int inRight) {        if (preLeft > preRight || inLeft > inRight) {            return null;        }        int rootval = preorder[preLeft];        //简历根节点        TreeNode root = new TreeNode(rootval);        int pIndex = map.get(rootval);        //构造左子树        root.left = buildTreedfs(preorder, preLeft + 1, pIndex - inLeft + preLeft, map, inLeft, pIndex - 1);        //构造右子树        root.right = buildTreedfs(preorder, pIndex - inLeft + preLeft + 1, preRight, map, pIndex + 1, inRight);        return root;    }}
    
   

package 计算机程序算法分类.dfs深度优先广度优先问题;import java.util.HashMap;import java.util.Map;/** * @Classname 前中序数组构造二叉树 * @Description TODO * @Date 2021/4/12 15:50 * @Created by xjl */public class 中后序数组构造二叉树 {    public class TreeNode {        int val;        TreeNode left;        TreeNode right;        public TreeNode(int val) {            this.val = val;        }    }    public TreeNode buildTree(int[] inorder, int[] postorder) {        int inLen = inorder.length - 1;        int poLen = postorder.length - 1;        if (inLen != poLen) {            return null;        }        Map
   
     map = new HashMap<>();        for (int i = 0; i < inorder.length; i++) {            map.put(inorder[i], i);        }        return dfs(postorder, 0, poLen, map, 0, inLen);    }    /**     * @description TODO 采用的和中序和谦虚的方式是一样的     * @param: postorder     * @param: PLeft     * @param: PRight     * @param: map     * @param: inLeft     * @param: inRight     * @date: 2021/4/13 10:54     * @return: 计算机程序算法分类.dfs深度优先广度优先问题.中后序数组构造二叉树.TreeNode     * @author: xjl    */    private TreeNode dfs(int[] postorder, int PLeft, int PRight, Map
    
      map, int inLeft, int inRight) {        if (PLeft > PRight || inLeft > inRight) {            return null;        }        int rootval = postorder[PRight];        TreeNode root = new TreeNode(rootval);        int Index = map.get(rootval);        root.left = dfs(postorder, PLeft, Index + PLeft-inLeft- 1, map, inLeft, Index - 1);        root.right = dfs(postorder, Index + PLeft-inLeft, PRight - 1, map, Index + 1, inRight);        return root;    }}
    
   

返回与给定的前序和后序遍历匹配的任何二叉树。 pre 和 post 遍历中的值是不同的正整数。

class Solution {    public TreeNode constructFromPrePost(int[] pre, int[] post) {        if(pre==null || pre.length==0) {            return null;        }        return dfs(pre,post);    }	    private TreeNode dfs(int[] pre,int[] post) {        if(pre==null || pre.length==0) {            return null;        }        //数组长度为1时，直接返回即可        if(pre.length==1) {            return new TreeNode(pre[0]);        }        //根据前序数组的第一个元素，创建根节点         TreeNode root = new TreeNode(pre[0]);        int n = pre.length;        for(int i=0;i

转载地址：http://gwjh.baihongyu.com/