力扣106. 从中序与后序遍历序列构造二叉树
Problem: 106. 从中序与后序遍历序列构造二叉树
文章目录
- 题目描述
- 思路
- 复杂度
- Code
题目描述
思路
具体思路参考：
Problem: 力扣105. 从前序与中序遍历序列构造二叉树
再后序遍历中：每次取int rootVal = postorder[postEnd];构造根节点；左子树的范围是build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1)；右子树范围为build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1)
复杂度
时间复杂度:
O ( n ) O(n) O(n)；其中 n n n为树节点的个数
空间复杂度:
O ( h e i g h ) O(heigh) O(heigh)；其中 h e i g h t height height为树的高度
Code
/*** 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> valToIndex = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {for (int i = 0; i < inorder.length; ++i) {valToIndex.put(inorder[i], i);}return build(inorder, 0, inorder.length - 1,postorder, 0, postorder.length - 1);}TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {if (inStart > inEnd) {return null;}// The value of the root node is the last element of the post-order traversal groupint rootVal = postorder[postEnd];// rootVal traverses the index in the group in medium orderint index = valToIndex.get(rootVal);// Number of nodes in the left subtreeint leftSize = index - inStart;TreeNode root = new TreeNode(rootVal);root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);return root;}
}