Construct Binary Tree from Preorder and Inorder Traversal
给一个pre order和 in order遍历的数组, 返回一个二叉树.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTree0(preorder, 0, preorder.length, inorder, 0, inorder.length); } private TreeNode buildTree0(int[] preorder, int ipre, int jpre, int[] inorder, int iin, int jin) { if(jpre <= ipre || jin <= iin) return null; TreeNode root = new TreeNode(preorder[ipre]); int i=iin; for(; i<jin; i++) { if(inorder[i] == preorder[ipre]) break; } root.left = buildTree0(preorder, ipre+1, ipre+1+i-iin, inorder, iin, i); root.right = buildTree0(preorder, ipre+1+i-iin, jpre, inorder, i+1, jin); return root; } } |