首页 > 代码库 > Construct Binary Tree from Inorder and Postorder Traversal
Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
根据树的中序（左根右）和后序遍历（左右根）构造一棵二叉树
参考：http://www.cnblogs.com/remlostime/archive/2012/10/29/2744738.html
后序遍历最后一个元素是根节点，通过根节点将中序遍历数组分为两个数组，分别是左子树和右子树节点的集合，在进行递归调用
这里用的下标，节约空间
1 public class Solution { 2 public TreeNode buildTree(int[] inorder, int[] postorder) { 3 TreeNode root; 4 if(0 == inorder.length) 5 return null; 6 else 7 return createTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1); 8 9 }10 private TreeNode createTree(int []inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd){11 if(inStart > inEnd)12 return null;13 int value_root = postorder[postEnd]; //根节点的值14 int index = 0; //根节点在中序遍历中的索引值15 for(int i = inStart; i <= inEnd; i++){ //找出根节点在终须遍历中的索引值16 if(postorder[postEnd] == inorder[i]){17 index = i;18 break;19 }20 }21 int length_leftTree = index - inStart; //左子树的长度22 TreeNode leftTreeRoot = createTree(inorder, postorder, inStart, index - 1, postStart, postStart + length_leftTree - 1); 23 TreeNode rightTreeRoot = createTree(inorder, postorder, index + 1, inEnd, postStart + length_leftTree, postEnd - 1);24 25 TreeNode root = new TreeNode(value_root);26 27 root.left = leftTreeRoot;28 root.right = rightTreeRoot;29 30 return root;31 }32 }
Construct Binary Tree from Inorder and Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。