首页 > 代码库 > Leetcode-Construct Binary Tree from inorder and postorder travesal
Leetcode-Construct Binary Tree from inorder and postorder travesal
Given inorder and postorder traversal of a tree, construct the binary tree.
Solution:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public TreeNode buildTree(int[] inorder, int[] postorder) {12 if (inorder.length==0)13 return null;14 15 int len = inorder.length;16 TreeNode root = buildTreeRecur(inorder,postorder,0,len-1,0,len-1);17 return root;18 }19 20 //Build tree for current list, i.e., inorder[inHead] to inorder[inEnd].21 public TreeNode buildTreeRecur(int[] inorder, int[] postorder, int inHead, int inEnd, int postHead, int postEnd){22 if (inHead==inEnd){23 TreeNode root = new TreeNode(inorder[inHead]);24 return root;25 }26 27 int curRoot = postorder[postEnd];28 int index = -1;29 for (int i=inHead;i<=inEnd;i++)30 if (inorder[i]==curRoot){31 index = i;32 break;33 }34 int leftNodeNum = index-inHead;35 36 37 int leftInHead = inHead;38 int leftInEnd = inHead+leftNodeNum-1;39 int rightInHead = index+1;40 int rightInEnd = inEnd; 41 42 43 int leftPostHead = postHead;44 int leftPostEnd = postHead+leftNodeNum-1;45 int rightPostHead = leftPostEnd+1;46 int rightPostEnd = postEnd-1;47 48 TreeNode root = new TreeNode(curRoot);49 TreeNode leftChild = null;50 if (leftInEnd>=inHead){51 leftChild = buildTreeRecur(inorder,postorder,leftInHead,leftInEnd,leftPostHead,leftPostEnd);52 root.left = leftChild;53 }54 55 TreeNode rightChild = null;56 if (rightInHead<=inEnd){57 rightChild = buildTreeRecur(inorder,postorder,rightInHead,rightInEnd,rightPostHead,rightPostEnd);58 root.right = rightChild;59 }60 61 return root;62 }63 }
We need to be very carefull about how to count the start and end of the left sub-tree and the right-sub tree. Especially detecting the case that some sub-tree is void.
A better way is to calculate the number of nodes in left and right tree first, then find out the range, like this:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public TreeNode buildTree(int[] inorder, int[] postorder) {12 if (inorder.length==0)13 return null;14 15 int len = inorder.length;16 TreeNode root = buildTreeRecur(inorder,postorder,0,len-1,0,len-1);17 return root;18 }19 20 //Build tree for current list, i.e., inorder[inHead] to inorder[inEnd].21 public TreeNode buildTreeRecur(int[] inorder, int[] postorder, int inHead, int inEnd, int postHead, int postEnd){22 if (inHead==inEnd){23 TreeNode root = new TreeNode(inorder[inHead]);24 return root;25 }26 27 int curRoot = postorder[postEnd];28 TreeNode root = new TreeNode(curRoot);29 TreeNode leftChild = null;30 TreeNode rightChild = null;31 32 int index = -1;33 for (int i=inHead;i<=inEnd;i++)34 if (inorder[i]==curRoot){35 index = i;36 break;37 }38 int leftNodeNum = index-inHead;39 int rightNodeNum = inEnd-index;40 41 if (leftNodeNum>0){42 int leftInHead = inHead;43 int leftInEnd = inHead+leftNodeNum-1;44 int leftPostHead = postHead;45 int leftPostEnd = postHead+leftNodeNum-1;46 leftChild = buildTreeRecur(inorder,postorder,leftInHead,leftInEnd,leftPostHead,leftPostEnd);47 root.left = leftChild;48 }49 50 51 if (rightNodeNum>0){52 int rightInHead = index+1;53 int rightInEnd = inEnd;54 int rightPostHead = postEnd-rightNodeNum;55 int rightPostEnd = postEnd-1;56 rightChild = buildTreeRecur(inorder,postorder,rightInHead,rightInEnd,rightPostHead,rightPostEnd);57 root.right = rightChild;58 }59 60 return root;61 }62 }
Leetcode-Construct Binary Tree from inorder and postorder travesal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。