106. 从中序与后序遍历序列构造二叉树.md

106. 从中序与后序遍历序列构造二叉树

解题思路

• 定义了一个 TreeNode 类表示二叉树节点，包含了节点的值 val 以及左右子节点的引用 left 和 right。
• 创建了一个 HashMap，用于存储中序遍历中节点值到索引值的映射关系，便于后续快速查找。
• 实现了 buildTree 方法，该方法接收中序遍历数组 inorder 和后序遍历数组 postorder 作为输入，返回构造好的二叉树的根节点。 在 buildTree 方法中，首先遍历中序遍历数组，将节点值与其索引值存入 valIndex 哈希表中。
• 调用 build 方法进行递归构造二叉树。该方法接收中序遍历数组的起始和结束索引 inStart 和 inEnd，后序遍历数组的起始和结束索引 postStart 和 postEnd。
• 如果 inStart 大于 inEnd，说明当前子树为空，直接返回 null。
• 取后序遍历数组的最后一个元素作为当前子树的根节点值 rootVal。
• 根据 rootVal 在中序遍历数组中的索引值 index，将中序遍历数组分为左右两个子数组。
• 计算左子树的节点数量 leftSize，用于确定左子树在后序遍历数组中的范围。
• 递归构造左右子树，根据左子树节点数量确定左右子树在后序遍历数组中的范围。
• 返回根节点 root。

/**
 * 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 {

    // 存储中序遍历中 值到索引值的映射
    HashMap<Integer,Integer> valIndex = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i = 0; i < inorder.length; i++){
            valIndex.put(inorder[i],i);
        }
        
        return build(inorder,0,inorder.length - 1,
        postorder,0,postorder.length - 1);
    }

        TreeNode build(int[] inorder,int inStart,int inEnd,
    int[] postorder,int postStart,int postEnd){
        if(inStart > inEnd){
            return null;
        }

        // root节点对应的值就是后序遍历数组的最后一个元素
        int rootVal = postorder[postEnd];

        // 计算根节点在中序遍历的索引 根据此然后划分左右子树
        int index = valIndex.get(rootVal);

        // 构造根节点
        TreeNode root = new TreeNode(rootVal);
        int leftSize = index - inStart;

        // 递归构造左右子树
        root.left = build(inorder,inStart,index - 1,
        postorder,postStart,postStart + leftSize - 1);

        root.right = build(inorder,index + 1,inEnd,
        postorder,postStart + leftSize,postEnd - 1);

        return root;
    }
}