Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
ref: http://fisherlei.blogspot.com/2013/01/leetcode-construct-binary-tree-from.html
注意 preorder根节点的下标是 pStart, 不要写成 0
注意 preorder 注意左子树和右子树开始的index
左子树是 pStart+1 + (rootIndex-1 - iStart) // inorder中 左子树的长度
右子树是 pStart+1 + (rootIndex-1 - iStart) +1
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || inorder == null) { return null; } int preLen = preorder.length; int inLen = inorder.length; if (preLen == 0 || inLen == 0) { return null; } return constructTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1); } public static TreeNode constructTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { int rootValue = preorder[preStart]; TreeNode root = new TreeNode(rootValue); root.left = null; root.right = null; if (preStart == preEnd && preorder[preStart] == inorder[inStart]) { return root; } int i = inStart; for (; i <= inEnd; i++) { if (rootValue == inorder[i]) { break; } } int leftLen = i - inStart; // 如果左子树不为空 if (leftLen > 0) { root.left = constructTree(preorder, preStart + 1, preStart + leftLen, inorder, inStart, i - 1); } // 如果右子树不为空 if (inEnd > i) { root.right = constructTree(preorder, preStart + leftLen + 1, preEnd, inorder, i + 1, inEnd); } return root; } }