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

力扣 105. 从前序与中序遍历序列构造二叉树

题目说明

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

提示：

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

示例

示例 1:

1 2	Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

示例 2:

1 2	Input: preorder = [-1], inorder = [-1] Output: [-1]

笔者理解

此题是一道二叉树算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现我们只需要分治构建节点以及左右子树即可，让我们来看看具体如何实现的吧。

实现

/**
 * 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) {
        int n = preorder.length;

        TreeNode result = buildNode(0, n, 0, n, preorder, inorder);

        return result;
    }

    /**
     * 建立节点
     *
     * @param preLeft  前序左边界
     * @param preRight 前序右边界
     * @param inLeft   中序左边界
     * @param inRight  中序右边界
     * @param preorder 前序序列
     * @param inorder  中序序列
     */
    public TreeNode buildNode(int preLeft, int preRight, int inLeft, int inRight, int[] preorder, int[] inorder) {
        // 左右区间重合，无节点
        if (preLeft == preRight) {
            return null;
        }

        // 当前根节点
        int now = preorder[preLeft];
        TreeNode result = new TreeNode(now);

        // 计算左子树的节点个数
        int tick = 0;
        for (int i = inLeft; i < inRight; i++) {
            if (inorder[i] == now) {
                break;
            }
            tick++;
        }

        // 分别构建左右节点
        result.left = buildNode(preLeft + 1, preLeft + tick + 1, inLeft, inLeft + tick, preorder, inorder);
        result.right = buildNode(preLeft + tick + 1, preRight, inLeft + tick + 1, inRight, preorder, inorder);

        return result;
    }
}