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

题目描述：根据一棵树的中序遍历与后序遍历构造二叉树。

代码实现

递归实现

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

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

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

        //3. 后续最后一个节点为二叉树根节点
        TreeNode root = new TreeNode(postorder[rootIdx]);

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

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

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

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