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

39次阅读

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

题目形容：给定一棵树的前序遍历 preorder 与中序遍历 inorder。请结构二叉树并返回其根节点。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：递归法

通过递归的形式结构二叉树，递归过程如下：

如果前序遍历序列或者中序遍历序列为空时，间接返回空树；

因为前序遍历序列的第一个值为根节点，所以首先失去根节点；

而后依据中序遍历中根节点的地位失去根节点的左右子树的节点的数量 leftCount 和 rightCount；

而后递归调用该办法失去以后根节点的左右子树；

最初返回根节点。

import com.kaesar.leetcode.TreeNode;

import java.util.Arrays;

public class LeetCode_105 {public static TreeNode buildTree(int[] preorder, int[] inorder) {
        // 以后序遍历序列或者中序遍历序列为空时，间接返回空树
        if (preorder == null || preorder.length == 0) {return null;}
        // 前序遍历序列的第一个值为根节点
        TreeNode root = new TreeNode(preorder[0]);
        // 左子树节点的数量
        int leftCount;
        // 中序遍历序列中，根节点右边的节点都是根节点左子树的节点
        for (leftCount = 0; leftCount < inorder.length; leftCount++) {if (inorder[leftCount] == preorder[0]) {break;}
        }
        // 依据左子树节点数和总的节点数计算右子树节点的数量
        int rightCount = inorder.length - 1 - leftCount;

        // 递归调用失去以后节点的左右子树
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, leftCount + 1), Arrays.copyOfRange(inorder, 0, leftCount));
        root.right = buildTree(Arrays.copyOfRange(preorder, leftCount + 1, preorder.length), Arrays.copyOfRange(inorder, leftCount + 1, inorder.length));
        return root;
    }

    public static void main(String[] args) {int[] preorder = new int[]{3, 9, 20, 15, 7};
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        buildTree(preorder, inorder).print();}
}