关于java:LeetCode106从中序与后序遍历序列构造二叉树

5次阅读

共计 1246 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：依据一棵树的中序遍历与后序遍历结构二叉树。

留神:
你能够假如树中没有反复的元素。

示例阐明请见 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();}
}