本文主要是介绍106.从中序与后序遍历构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
思路：
- 中序遍历数组中，找到一个根节点，那么其前为其左子树，其后为其右子树
- 后序遍历数组从后像前依次为 根节点-右-左
- 根据后序数组得到根节点，通过map（保存inorder数据及下标，以便返回根节点在inorder中的位置，从而区分左右子树，以便再次进行递归）找到inorder中的根节点位置，将其值加入到root中。
class Solution{int post_idx;int[] inorder;int[] postorder;Map<Integer, Integer> map = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder){this.inorder = inorder;this.postorder = postorder;post_idx = postorder.length - 1;int idx = 0;// 将中序数组传进map中for(int val : inorder){map.put(val, idx++);}return helper(0, post_idx);} public TreeNode helper(int l, int r){if(l > r) return null;int root_val = postorder[post_idx--];// 没有post_idx--,报错了StackOverflowErrorTreeNode root = new TreeNode(root_val);int idx = map.get(root_val);root.right = helper(idx + 1, r);root.left = helper(l, idx - 1);return root;}
}
这篇关于106.从中序与后序遍历构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
