给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
首先需要明确,怎样使用中序遍历和后序遍历来构成唯一的二叉树。
中序遍历:左根右
后序遍历:左右根
可知树的根一定是后序遍历的最后一个数。此时我们需要在中序遍历中找到这个数,即为根。以根为中心,左边是左子树,右边是右子树。
接下来的事情就可以交给递归,唯一的问题在于递归的传入参数了,即递归调用buildTree函数时,inorder和postorder又分别指数组的哪一段到哪一段。
假设当前根结点在inorder中的坐标为i,i左侧即为左子树,右侧即为右子树。用函数Arrays.copyOfRange可以对相应数组进行裁剪。
当寻找左子树时,inorder需要的坐标范围为[0, i),postorder需要的坐标范围也为[0, i);
当寻炸右子树时,inorder需要的坐标范围为[i+1, postorder.length),postorder需要的坐标范围也为[i, postorder.length-1)。
最后,当inorder和postorder中只剩下最后一个数时,说明当前子树建立完成,可以return。
实现代码如下:
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
TreeNode root = new TreeNode(postorder[postorder.length-1]);
//i用来寻找inorder中的根结点位置
int i=0;
while(inorder[i]!=postorder[postorder.length-1]) i++;
if(i>0) {//一定有左子树
root.left=buildTree(Arrays.copyOfRange(inorder, 0, i),
Arrays.copyOfRange(postorder,0,i));
}
if(i<postorder.length -1) {//一定有右子树
root.right=buildTree(Arrays.copyOfRange(inorder, i+1, postorder.length),
Arrays.copyOfRange(postorder,i,postorder.length-1));
}
//如果不满足上述两个if,就说明已经是最后一个结点了,可以返回了
return root;
}
}