力扣 106. 从中序与后序遍历序列构造二叉树
题目是 [106. 从中序与后序遍历序列构造二叉树(https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
使用中序遍历和后序遍历确定二叉树的结构,关键是知道后序遍历的最后一个节点是整个树的根节点。所以每次根据后序遍历的数组中的最后一个元素得到中序遍历中的根节点的索引,从而把中序遍历的数组分成左右两个子树。
注意这里的后序遍历数组的最后一个元素索引每次都会自减,因为每一次递归都会用掉当前后序遍历数组的最后一个元素。
因为要使用后序遍历数组的最后一个元素,所以要先构造出右子树,然后再构造左子树。
/**
* 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 {
int[] inorder;
int[] postorder;
int postRight;
Map<Integer, Integer> map;
public TreeNode myBuildTree(int inLeft, int inRight){
if(inRight<inLeft) return null;
TreeNode root=new TreeNode(postorder[postRight]);
int rootVal =postorder[postRight]; //根节点
int inorderRootIndex=map.get(rootVal); //在中序遍历中定位根节点的索引
postRight--;
root.right=myBuildTree(inorderRootIndex+1, inRight);
root.left=myBuildTree(inLeft, inorderRootIndex-1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.inorder=inorder;
this.postorder=postorder;
this.postRight=postorder.length-1;
int inlen=inorder.length;
map=new HashMap<>();
for(int i=0; i<inorder.length; i++){
map.put(inorder[i], i);
}
return myBuildTree(0, inlen-1);
}
}