【力扣每日一题】力扣889根据前序和后续遍历构造二叉树

本文主要是介绍【力扣每日一题】力扣889根据前序和后续遍历构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源

力扣889根据前序和后续遍历构造二叉树

题目概述

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

思路分析

左分支的头节点一定在前序遍历root节点的右边第一个，也是后序遍历序列右分支的最后一个节点。 于是我们在postOrder中找到一个节点，它的值==preOrder[1]（preOrder [0]为root节点）。 根据这个节点就可以划分出左右分支。

代码实现

public class Solution {public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {int length = preorder.length;if (length == 0) return null;TreeNode root = new TreeNode(preorder[0]);if (length == 1) return root;int leftSubTree = 0;for (int i = 0; i < length; ++i) {if (postorder[i] == preorder[1]) {leftSubTree = i + 1;}}root.left = constructFromPrePost(Arrays.copyOfRange(preorder, 1, leftSubTree+1),Arrays.copyOfRange(postorder, 0, leftSubTree));root.right = constructFromPrePost(Arrays.copyOfRange(preorder, leftSubTree+1, length),Arrays.copyOfRange(postorder, leftSubTree, length-1));return root;}
}

这篇关于【力扣每日一题】力扣889根据前序和后续遍历构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---