LintCode2016年8月8日算法比赛----中序遍历和后序遍历构造二叉树

时间:2021-07-22 02:13:05

中序遍历和后序遍历构造二叉树

题目描述

根据中序遍历和后序遍历构造二叉树

 注意事项

你可以假设树中不存在相同数值的节点
样例

给出树的中序遍历: [1,2,3] 和后序遍历: [1,3,2]

返回如下的树:

  2
/ \
1 3
算法分析:

给定同一课二叉树的中序和后序遍历数组,那么后序遍历数组的最后一个元素就是根节点的元素。在中序遍历数组中找到这个元素的index(能够找到这个唯一的index,依据就是树中不存在相同数值的节点),那么这个index就把中序遍历的数组分割成了左子树和右子树的数组两个部分。则中序遍历数组中,0index-1的数据为左子树的数据,index+1length-1的数据为右子树的数据;后序遍历数组中,0index-1的数据为左子树的数据,indexlength-2的数据为右子树的数据。(后序遍历的数组中的下标为length-1的数据为根节点数据)

Java算法实现:

/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/**
*@param inorder : A list of integers that inorder traversal of a tree
*@param postorder : A list of integers that postorder traversal of a tree
*@return : Root of a tree
*/
public static TreeNode buildTree(int[] inorder, int[] postorder) {
// write your code here
TreeNode root=makeTree(inorder, 0, inorder.length, postorder, 0, postorder.length); return root;
} public static TreeNode makeTree(int[] inorder,int startIn,int lenIn,int[] postorder,int startPos,int lenPos){
if(lenIn<1){
return null;
}
TreeNode root;
int rootVal=postorder[startPos+lenPos-1];//postorder中的最后一个元素就是当前处理的数据段的根节点
root=new TreeNode(rootVal);
int offset;
boolean isFound=false;
for(offset=0;offset<lenIn;offset++){ if(inorder[startIn+offset]==rootVal){
isFound=true;//标记确实找到了根节点
break;
}
}
if(!isFound)//如果不存在相等的情况,赢跳出该函数
return root;
//找到了根节点在 inorder 中的下标,将 inorder 分割为两部分:(1)--startIn~(startIn+offset-1)为左子树的数据
//(2)--(startIn+offset+1)~(startIn+lenIn-1)为右子树的数据
//同样,postorder中,也将数据分割为两部分:(1)--startPos~(startPos+offset-1)为左子树的数据
//(2)--(startPos+offset)~(startPos+lenPos-2)右子树的数据
root.left=makeTree(inorder, startIn, offset, postorder, startPos, offset);
root.right=makeTree(inorder, startIn+offset+1, lenIn-offset-1, postorder, startPos+offset, lenPos-offset-1);
return root;
}
}