本文主要是介绍【递归】889. 根据前序和后序遍历构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
889. 根据前序和后序遍历构造二叉树
解题思路
-
定义了一个二叉树节点类 TreeNode，包含节点值 val、左子节点 left 和右子节点 right。
-
在 Solution 类中定义了一个 HashMap 类型的成员变量 valToIndex，用于存储后序遍历的节点值和对应的索引。
-
constructFromPrePost 方法是构建二叉树的入口方法，接受前序遍历数组和后序遍历数组作为参数，返回构建好的二叉树。
-
在 constructFromPrePost 方法中，首先遍历后序遍历数组，将其中每个节点值和其索引存入 valToIndex 中。
-
然后调用 build 方法进行递归构建二叉树，传入前序遍历数组、后序遍历数组以及各自的起始和结束位置。
-
build 方法中，首先判断前序遍历起始位置是否超过了结束位置，如果是，则返回 null。
-
如果前序遍历起始位置等于结束位置，说明是叶子节点，直接创建并返回节点。
-
获取当前子树的根节点值和左子树根节点值。
-
根据左子树根节点值在后序遍历数组中的索引找到左子树的结束位置，进而确定左子树的大小。
-
创建当前子树的根节点。
-
递归构建左右子树，更新前序遍历和后序遍历的起始和结束位置，并将左右子树连接到根节点上。
-
最后返回根节点，完成整个二叉树的构建。
/*** 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 {// 存储中序遍历中 值到索引值的映射HashMap<Integer,Integer> valToIndex = new HashMap<>();public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {for (int i = 0; i < postorder.length; i++) {valToIndex.put(postorder[i], i);}return build(preorder, 0, preorder.length - 1,postorder, 0, postorder.length - 1);}TreeNode build(int[] preorder,int preStart,int preEnd,int[] postorder,int postStart,int postEnd){if(preStart > preEnd){return null;}if(preStart == preEnd){return new TreeNode(preorder[preStart]);}// 根节点int rootVal = preorder[preStart];// root.left 的值是先序遍历的第二个元素的值int leftRootVal = preorder[preStart + 1];// 找到左子树根节点的后序遍历的索引int index = valToIndex.get(leftRootVal);// 左子树的元素个数int leftSize = index - postStart + 1;// 先构造出当前根节点TreeNode root = new TreeNode(rootVal);// 递归构造左右子树root.left = build(preorder,preStart + 1,preStart + leftSize,postorder,postStart,index);root.right = build(preorder,preStart + leftSize + 1, preEnd,postorder,index + 1,postEnd - 1);return root;}}这篇关于【递归】889. 根据前序和后序遍历构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
