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

朱雀 2022-09-10 05:24 112阅读 0赞

Leetcode链接：[106. 从中序与后序遍历序列构造二叉树][106.]

### 题目描述 ###

> 根据一棵树的中序遍历与后序遍历构造二叉树。

注意:

> 你可以假设树中`没有重复的元素`。

例如，给出

> 中序遍历 inorder = \[9,3,15,20,7\]  
> 后序遍历 postorder = \[9,15,7,20,3\]

返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

### 源码 ###

/**
     * 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[] inorder, int[] postorder) {
        
            int n = inorder.length;
            int m = postorder.length;
    
            if(n != m) return null;
    
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < n; i ++){
        
                map.put(inorder[i], i);
            }
            return buildTree(postorder, 0, m - 1, map, 0, n - 1);
        }
    
        public TreeNode buildTree(int[] postorder, int postLeft, int postRight, Map<Integer, Integer> map, int inLeft, int inRight) {
        
            if(postLeft > postRight || inLeft > inRight) return null;
            int rootVal = postorder[postRight];
            TreeNode root = new TreeNode(rootVal);
            int pIndex = map.get(rootVal);
            root.left = buildTree(postorder, postLeft, pIndex - inRight + postRight - 1, map, inLeft, pIndex - 1);
            root.right = buildTree(postorder, pIndex - inRight + postRight, postRight - 1, map, pIndex + 1, inRight);
            return root;
        }
    }

[106.]: https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/