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

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

代码实现

递归实现

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, inorder, 0, inorder.length);
    }

    public TreeNode buildTree(int[] preorder, int rootIdx, int[] inorder, int start, int end) {
        //1. 判空
        if (start >= end) {
            return null;
        }

        //2. 单个节点直接返回
        if (start == end - 1) {
            return new TreeNode(inorder[start]);
        }

        //3. 前序第一个节点为二叉树根节点
        TreeNode root = new TreeNode(preorder[rootIdx]);

        //4. 寻找根节点在中序序列中的索引值
        int rootIdxInOrder = start;
        for (int idx = start; idx < end; idx++) {
            if (inorder[idx] == root.val) {
                rootIdxInOrder = idx;
                break;
            }
        }

        //5. 中序序列中根节点左部分节点构成左子树
        TreeNode leftNode = buildTree(preorder, rootIdx + 1, inorder, start, rootIdxInOrder);

        //6. 中序序列中根节点右部分节点构成右子树
        TreeNode rightNode = buildTree(preorder, rootIdx + 1 + rootIdxInOrder - start, inorder, rootIdxInOrder + 1, end);

        //7. 连接左右子树
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }
}