首页 > 代码库 > LeetCode Construct Binary Tree from Inorder and Postorder Traversal
LeetCode 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 * 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 int length=inorder.length;13 if (length==0) return null;14 int rootnumber=postorder[length-1];15 TreeNode root = new TreeNode(rootnumber);16 17 if (length==1) return root;18 int indexRoot = 0;19 for (int i = 0; i < length; i++) {20 if (inorder[i]==rootnumber){21 indexRoot=i;22 break;23 }24 }25 int[] left=new int[indexRoot];26 int[] leftPost=new int[indexRoot];27 int[] right=new int[length-indexRoot-1];28 int[] rightPost=new int[length-indexRoot-1];29 for (int i = 0; i < indexRoot; i++) {30 left[i]=inorder[i];31 leftPost[i]=postorder[i];32 }33 for (int i = indexRoot+1; i <length ; i++) {34 right[i-1-indexRoot]=inorder[i];35 rightPost[i-1-indexRoot]=postorder[i-1];36 }37 root.left=buildTree(left,leftPost);38 root.right=buildTree(right,rightPost);39 return root;40 }41 }
LeetCode Construct Binary Tree from Inorder and Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。