首页 > 代码库 > 44: Construct Binary Tree from Inorder and Postorder Traversal
44: Construct Binary Tree from Inorder and Postorder Traversal
/************************************************************************/
/* 44: Construct Binary Tree from Inorder and Postorder Traversal */
/************************************************************************/
/*
* Given inorder and postorder traversal of a tree, construct the binary tree.
*
* Note:
You may assume that duplicates do not exist in the tree.
* */
/*** 递归做法******************/
/*
* 问题：
*
* 1： 给出 中序与后序，是否能唯一确定一棵二叉树？（在没有重复节点值的情况下）？
* 2： 给出 中序与前序，是否能唯一确定一棵二叉树？（在没有重复节点值的情况下）？
* 自己测试了，出现了不能唯一确定一棵树的情况，待检测
* */
public TreeNode buildTreeByPost_In(int[] inorder, int[] postorder) { TreeNode root=null; root=helper_PostAndIn(postorder.length-1,0,postorder.length-1,postorder,inorder); return root; } private TreeNode helper_PostAndIn(int PostStart, int inStart, int inEnd, int[] postorder, int[] inorder) { if (PostStart < 0 || inStart > inEnd) { return null; } TreeNode root = new TreeNode(postorder[PostStart]); int inIndex = 0; // Index of current root in inorder for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.val) { inIndex = i; break; } } root.right = helper_PostAndIn(PostStart-1, inIndex + 1, inEnd, postorder, inorder); root.left = helper_PostAndIn(PostStart-(inEnd-inIndex+1), inStart, inIndex - 1, postorder, inorder); return root; }
44: Construct Binary Tree from Inorder and Postorder Traversal