105 题目：
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Return the following binary tree:
3 / \ 9 20 / \ 15 7其实就是一年半前写的这玩意儿：https://blog.csdn.net/qq_37333947/article/details/88704692。
大概了解怎么做了，但是写代码还是有点小问题，首先是不确定到底要不要helper里面把preorder和inorder的start/end全都加上，后来为了图省心还是都加上了，但是这个index的边界搞了我半天才debug出来，很多小细节在里面。感觉还是以前那种可以直接construct一个数组传进去的比较方便。
Runtime: 3 ms, faster than 57.32% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 38.9 MB, less than 7.97% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
/** * 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) { if (preorder.length == 0 || inorder.length == 0) { return null; } return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1); } public TreeNode helper(int[] preorder, int[] inorder, int start1, int end1, int start2, int end2) { if (start1 > end1) { return null; } TreeNode node = new TreeNode(preorder[start1]); int rootIndex = findRoot(inorder, preorder[start1]); int leftLength = rootIndex - start2; node.left = helper(preorder, inorder, start1 + 1, start1 + leftLength, start2, rootIndex - 1); node.right = helper(preorder, inorder, start1 + 1 + leftLength, end1, rootIndex + 1, end2); return node; } private int findRoot(int[] inorder, int num) { for (int i = 0; i < inorder.length; i++) { if (inorder[i] == num) { return i; } } return -1; } }然后写了个不用helper直接每次取subarray的，被index弄的更加自闭了……但是确实感觉代码要整洁一点，但似乎效率并不高。
Runtime: 11 ms, faster than 6.56% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 39.2 MB, less than 7.97% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
/** * 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) { if (preorder.length == 0 || inorder.length == 0) { return null; } TreeNode node = new TreeNode(preorder[0]); int rootIndex = findRoot(inorder, preorder[0]); int leftLength = rootIndex; int[] leftPreorder = new int[leftLength]; int[] leftInorder = new int[leftLength]; for (int i = 0; i < leftLength; i++) { leftPreorder[i] = preorder[i + 1]; leftInorder[i] = inorder[i]; } int rightLength = preorder.length - rootIndex - 1; int[] rightPreorder = new int[rightLength]; int[] rightInorder = new int[rightLength]; for (int i = 0; i < rightLength; i++) { rightPreorder[i] = preorder[rootIndex + i + 1]; rightInorder[i] = inorder[rootIndex + i + 1]; } node.left = buildTree(leftPreorder, leftInorder); node.right = buildTree(rightPreorder, rightInorder); return node; } private int findRoot(int[] inorder, int num) { for (int i = 0; i < inorder.length; i++) { if (inorder[i] == num) { return i; } } return -1; } }还有别的方法就先不看了。
106题目：
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7] postorder = [9,15,7,20,3]Return the following binary tree:
3 / \ 9 20 / \ 15 7本质上和105一样，只是postorder的根在最后，preorder的根在最前，于是用上面的第二种方法，算下一次的postorder的数组的时候不需要像preorder一样+1（就是留出根在前面的位置）。
Runtime: 11 ms, faster than 7.01% of Java online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
Memory Usage: 39.8 MB, less than 9.09% of Java online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
/** * 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[] inorder, int[] postorder) { if (postorder.length == 0 || inorder.length == 0) { return null; } int lastIndex = inorder.length - 1; TreeNode node = new TreeNode(postorder[lastIndex]); int rootIndex = findRoot(inorder, postorder[lastIndex]); int leftLength = rootIndex; int[] leftPostorder = new int[leftLength]; int[] leftInorder = new int[leftLength]; for (int i = 0; i < leftLength; i++) { leftPostorder[i] = postorder[i]; // no +1 leftInorder[i] = inorder[i]; } int rightLength = postorder.length - rootIndex - 1; int[] rightPostorder = new int[rightLength]; int[] rightInorder = new int[rightLength]; for (int i = 0; i < rightLength; i++) { rightPostorder[i] = postorder[rootIndex + i]; // no +1 rightInorder[i] = inorder[rootIndex + i + 1]; } node.left = buildTree(leftInorder, leftPostorder); node.right = buildTree(rightInorder, rightPostorder); return node; } private int findRoot(int[] inorder, int num) { for (int i = 0; i < inorder.length; i++) { if (inorder[i] == num) { return i; } } return -1; } }写解法1依旧被index搞的头昏脑胀，但跟preorder的比起来也就是postorder的整体index往前挪了一位。
Runtime: 3 ms, faster than 52.27% of Java online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
Memory Usage: 39 MB, less than 9.09% of Java online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
/** * 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[] inorder, int[] postorder) { if (postorder.length == 0 || inorder.length == 0) { return null; } return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1); } private TreeNode helper(int[] inorder, int[] postorder, int start1, int end1, int start2, int end2) { if (start1 > end1 || start2 > end2) { return null; } TreeNode node = new TreeNode(postorder[end2]); int rootIndex = findRoot(inorder, postorder[end2]); int leftLength = rootIndex - start1; node.left = helper(inorder, postorder, start1, rootIndex - 1, start2, start2 + leftLength - 1); node.right = helper(inorder, postorder, rootIndex + 1, end1, start2 + leftLength, end2 - 1); return node; } private int findRoot(int[] inorder, int num) { for (int i = 0; i < inorder.length; i++) { if (inorder[i] == num) { return i; } } return -1; } }
