根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3 / 9 20 / 15 7
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(preorder, inorder, 0, 0, preorder.length-1); } public TreeNode helper(int[] preorder, int[] inorder, int cur, int left, int right){ if(left>right) return null; TreeNode tn = new TreeNode(preorder[cur]); int i = left; for(; i<=right; i++) if(inorder[i]==preorder[cur]) break; tn.left = helper(preorder, inorder, cur+1, left, i-1); tn.right = helper(preorder, inorder, cur+i-left+1, i+1, right); return tn; } }
方法二:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { int prelen = preorder.length; int inlen = inorder.length; if(prelen!=inlen) { throw new RuntimeException("Incorrect input data"); } HashMap<Integer,Integer> map = new HashMap<>(); for(int i=0;i<inlen;i++) { map.put(inorder[i],i); } return buildTree(preorder,0,prelen-1,map,0,inlen-1); } /** * @param preorder 前序遍历序列 * @param preLeft 前序遍历序列子区间的左边界,可以取到 * @param preRight 前序遍历序列子区间的右边界,可以取到 * @param map 在中序遍历序列里,数值与小标对应关系 * @param inLeft 中序遍历序列子区间的左边界,可以取到 * @param inRight 中序遍历序列子区间的右边界,可以取到 * @return */ private TreeNode buildTree(int[] preorder, int preLeft,int preRight, Map<Integer,Integer> map, int inLeft,int inRight) { if( preLeft > preRight || inLeft > inRight) { return null; } int rootVal = preorder[preLeft]; TreeNode root = new TreeNode(rootVal); int pIndex = map.get(rootVal); root.left = buildTree(preorder,preLeft+1,pIndex-inLeft+preLeft,map,inLeft,pIndex-1); root.right = buildTree(preorder,pIndex-inLeft+preLeft+1,preRight,map,pIndex+1,inRight); return root; } }
方法二简化:
class Solution { HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for(int i =0;i< inorder.length;i++) { map.put(inorder[i],i); } return buildTree(preorder,0,preorder.length-1,0,inorder.length-1); } public TreeNode buildTree(int[] preorder,int preLeft,int preRight,int inLeft,int inRight) { if( preLeft > preRight || inLeft > inRight) return null; int rootVal = preorder[preLeft]; TreeNode root = new TreeNode(rootVal); int pIndex = map.get(rootVal); root.left = buildTree(preorder,preLeft+1,preLeft+pIndex-inLeft,inLeft,pIndex-1); root.right=buildTree(preorder,preLeft+pIndex-inLeft+1,preRight,pIndex+1,inRight); return root; } }
简化:(不好理解。没有看明白)
class Solution { HashMap<Integer,Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for(int i=0;i<inorder.length;i++) { map.put(inorder[i],i); } return helper(preorder,0,0,preorder.length-1); } public TreeNode helper(int [] preorder,int cur,int left,int right) { if(left > right) return null; int rootval = preorder[cur]; TreeNode root = new TreeNode(rootval); int i = map.get(rootval); root.left = helper(preorder,cur+1,left,i-1); root.right = helper(preorder,cur+i-left+1,i+1,right); return root; } }