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

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

【LeetCode-106-从中序与后序遍历序列构造二叉树】题目描述：根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归

根据中序遍历和后序遍历的性质，通过递归的方式求解，递归的过程如下：

首先，如果中序遍历序列或后序遍历序列为空，直接返回空树；

因为后序遍历序列的最后一个值为根节点，所以首先根据这个初始化得到当前的根节点root；

然后根据根节点root在中序遍历序列中的位置，根节点前面的值都是当前根节点的左子树节点，得到当前根节点左右子树节点的数量；

然后通过调用递归方法得到当前根节点的左右子树；

最后返回root即为还原后的树。

import com.kaesar.leetcode.TreeNode; import java.util.Arrays; public class LeetCode_106 { public static TreeNode buildTree(int[] inorder, int[] postorder) { // 如果中序遍历序列或后序遍历序列为空，直接返回空树 if (inorder == null || inorder.length == 0) { return null; } // 后序遍历序列的最后一个值为根结点的值 int rootVal = postorder[postorder.length - 1]; TreeNode root = new TreeNode(rootVal); int leftCount = 0; // 中序遍历序列前面的值为左子树的节点，得到左子树的节点数量 for (int val : inorder) { if (val != rootVal) { leftCount++; } else { break; } } // 递归得到当前根节点的左右子树 root.left = buildTree(Arrays.copyOfRange(inorder, 0, leftCount), Arrays.copyOfRange(postorder, 0, leftCount)); root.right = buildTree(Arrays.copyOfRange(inorder, leftCount + 1, inorder.length), Arrays.copyOfRange(postorder, leftCount, inorder.length - 1)); return root; }public static void main(String[] args) { // 测试用例 // 中序遍历序列 int[] inorder = new int[]{9, 3, 15, 20, 7}; // 后序遍历序列 int[] postorder = new int[]{9, 15, 7, 20, 3}; buildTree(inorder, postorder).print(); } }