代码拉取完成,页面将自动刷新
package com.nateshao.leetcode.binary_tree.code13_889_constructFromPrePost;
import java.util.HashMap;
/**
* @date Created by 邵桐杰 on 2022/4/30 21:41
* @微信公众号 千羽的编程时光
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitlab.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description:
* 889. 根据前序和后序遍历构造二叉树
* 给定两个整数数组,preorder 和 postorder ,其中 preorder 是一个具有 无重复 值的二叉树的前序遍历,
* postorder 是同一棵树的后序遍历,重构并返回二叉树。
*
* 如果存在多个答案,您可以返回其中 任何 一个。
*
* 示例 1:
* 输入:preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
* 输出:[1,2,3,4,5,6,7]
*
* 示例 2:
* 输入: preorder = [1], postorder = [1]
* 输出: [1]
*/
public class Solution {
// 存储 postorder 中值到索引的映射
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);
}
// 定义:根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]
// 构建二叉树,并返回根节点。
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]);
}
// root 节点对应的值就是前序遍历数组的第一个元素
int rootVal = preorder[preStart];
// root.left 的值是前序遍历第二个元素
// 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
// 确定 preorder 和 postorder 中左右子树的元素区间
int leftRootVal = preorder[preStart + 1];
// leftRootVal 在后序遍历数组中的索引
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;
}
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;
}
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。