（分治算法5）leecode 106 从中序和后续遍历序列构成二叉树

本文主要是介绍（分治算法5）leecode 106 从中序和后续遍历序列构成二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

分治递归算法

后序遍历的次序: 左-右-中
中序遍历的次序：左-中-右
可以发现，后续遍历的最后一个节点是该序列对应树或者子树的根节点root。
从中序遍历中可以找到root的坐标（无重复元素），那么中序遍历中该坐标的左边就是root中左子树的中序遍历序列，右边就是root右子树的中序遍历序列。
而在后序遍历中，可以依据中序遍历中得到的左子树序列长度切分出root左子树和右子树的后序遍历序列；
这样我们就分别得到了root的左子树的后序序列，中序序列，以及root右子树的后序序列以及中序序列
也就是切分成了子问题并且进行递归求解；

解题方法

1）使用递归，因为树或者子树的后序遍历和中序遍历序列在数组中都是连续的，所以我们可以使用边界来标记序列的长度
2）为了快速定位root在中序遍历中的位置，我们可以使用哈希表进行辅助；
3) 递归终止条件为序列的长度小于等于0，这时候返回NULL即可

复杂度

时间复杂度：O（n）
空间复杂度:O(n+log(n))

/*** 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 {Map<Integer, Integer> map;public TreeNode buildTree(int[] inorder, int[] postorder) {int n = inorder.length;map = new HashMap<> ();for (int i = 0; i < n; ++i) {map.put(inorder[i], i);}return dfs(inorder, 0, n - 1, postorder, 0 , n - 1);}private TreeNode dfs(int[] inorder, int il, int ir, int[] postorder, int pl, int pr) {if (pl > pr) {return null;}TreeNode root = new TreeNode(postorder[pr]);int mid = map.get(root.val);int leftLength = mid - il;TreeNode left = dfs(inorder, il, mid - 1, postorder, pl, pl + leftLength - 1);TreeNode right = dfs(inorder, mid + 1, ir, postorder, pl + leftLength, pr - 1);root.left = left;root.right = right;return root;}
}