106. 从中序与后序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150

思路：我们知道后序的顺序是左右根，所以后序数组的最后一个一定是根节点，然后中序是左根右，我们就可以拿着找到的根节点将中序分为两部分，这两部分分别是左子树和右子树，我们可以得到左右子树的节点个数，这样我们就可以在后序数组中找到对应的部分，然后对每部分分别执行上述操作。

class Solution {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;}}public TreeNode buildTree(int[] inorder, int[] postorder) {if(inorder.length == 0 || postorder.length == 0)return null;return method(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);}public TreeNode method(int[] inorder, int[] postorder, int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {// 找到传入部分的根节点TreeNode node = new TreeNode(postorder[postorderEnd]);// 只有一个节点的时候返回if(inorderStart == inorderEnd) {return node;}int inorderNextStart_L = 0, inorderNextEnd_L = 0; // 当前节点的左子树在中序中的下标范围int inorderNextStart_R = 0, inorderNextEnd_R = 0; // 当前节点的右子树在中序中的下标范围int postorderNextStart_L = 0, postorderNextEnd_L = 0; // 当前节点的左子树在后序中的下标范围int postorderNextStart_R = 0, postorderNextEnd_R = 0; // 当前节点的右子树在后序中的下标范围// 找到根节点在中序中的位置for(int i = inorderStart; i <= inorderEnd; i++) {if(inorder[i] == postorder[postorderEnd]) {inorderNextStart_L = inorderStart;inorderNextEnd_L = i - 1;inorderNextStart_R = i + 1;inorderNextEnd_R = inorderEnd;break;}}// 找到右子树在后序中的下标范围（因为右子树靠近根，我们可以通过长度直接得到范围）int rightTreeSize = inorderNextEnd_R - inorderNextStart_R + 1;postorderNextEnd_R = postorderEnd - 1;postorderNextStart_R = postorderNextEnd_R - rightTreeSize + 1;postorderNextStart_L = postorderStart;postorderNextEnd_L = postorderNextStart_R - 1;//传入左子树部分（注意范围，不要越界）if(check(inorderNextEnd_L, inorderStart, inorderEnd) && check(inorderNextStart_L, inorderStart, inorderEnd) && check(postorderNextEnd_L, postorderStart, postorderEnd) && check(postorderNextStart_L, postorderStart, postorderEnd))node.left = method(inorder, postorder, inorderNextStart_L, inorderNextEnd_L, postorderNextStart_L, postorderNextEnd_L);//传入右子树部分if(check(inorderNextEnd_R, inorderStart, inorderEnd) && check(inorderNextStart_R, inorderStart, inorderEnd) && check(postorderNextEnd_R, postorderStart, postorderEnd) && check(postorderNextStart_R, postorderStart, postorderEnd))node.right = method(inorder, postorder, inorderNextStart_R, inorderNextEnd_R, postorderNextStart_R, postorderNextEnd_R);return node;}public boolean check(int x, int l, int r) {return x >= l && x <= r;}public static void main(String[] args) {int[] inorder = {2,1};int[] postorder = {2,1};new Solution().buildTree(inorder, postorder);}
}