Construct Binary Tree from Inorder and Postorder Traversal
问题:
Given inorder and postorder traversal of a tree, construct the binary tree.
思路:
dfs
我的代码:
public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if(inorder == null || inorder.length == 0) return null; if(inorder.length == 1) return new TreeNode(inorder[0]); int len = postorder.length; int target = postorder[len-1]; int index = getIndex(inorder, target); TreeNode root = new TreeNode(target); root.left = buildTree(Arrays.copyOfRange(inorder,0,index),Arrays.copyOfRange(postorder,0,index)); root.right = buildTree(Arrays.copyOfRange(inorder, index+1, len),Arrays.copyOfRange(postorder, index, len-1)); return root; } public int getIndex(int[] inorder, int target) { for(int i = 0; i < inorder.length; i++) { if(inorder[i] == target) return i; } return -1; } }
Construct Binary Tree from Inorder and Postorder Traversal
原文:http://www.cnblogs.com/sunshisonghit/p/4335933.html