【算法题解】48. 从中序与后序遍历序列构造二叉树

男娘i 2024-03-17 12:28 2阅读 0赞

> 这是一道 **中等难度** 的题  
>   
> https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

### 题目 ###

给定两个整数数组 `inorder` 和 `postorder`，其中 `inorder` 是二叉树的中序遍历，`postorder` 是同一棵树的后序遍历，请你构造并返回这颗 *二叉树* 。

**示例 1:**  
![19848d2b2c23de23ac77f3a00cadbd6c.png][]

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    输出：[3,9,20,null,null,15,7]

**示例 2:**

输入：inorder = [-1], postorder = [-1]
    输出：[-1]

**提示:**

*   1 < = i n o r d e r . l e n g t h < = 3000 1 <= inorder.length <= 3000 1<=inorder.length<=3000
 *   p o s t o r d e r . l e n g t h = = i n o r d e r . l e n g t h postorder.length == inorder.length postorder.length==inorder.length
 *   − 3000 < = i n o r d e r \[ i \] -3000 <= inorder\[i\] −3000<=inorder\[i\],  p o s t o r d e r \[ i \] < = 3000 postorder\[i\] <= 3000 postorder\[i\]<=3000
 *   i n o r d e r inorder inorder 和  p o s t o r d e r postorder postorder 都由 *不同* 的值组成
 *   p o s t o r d e r postorder postorder 中每一个值都在  i n o r d e r inorder inorder 中
 *   i n o r d e r inorder inorder *保证*是树的中序遍历
 *   p o s t o r d e r postorder postorder *保证*是树的后序遍历

--------------------

### 题解 ###

这道题和 [从前序与中序遍历序列构造二叉树][Link 1] 的解题思路是一样的。

使用后序遍历数组 `postorder` 确定根节点，然后使用中序遍历数组 `inorder` 划分左右子树。

以示例一为例：  
![image.png][]  
后序确定根节点 `root = 3` 。

![image.png][image.png 1]  
利用中序遍历数组划分左右子树，并得到左右子树的中序遍历。

![image.png][image.png 2]  
因为上一步知道了右子树的中序遍历，也就可以知道右子树的节点个数，假如是 `m`。

利用后序遍历数组，除去根节点后，从后往前依次取 `m` 个元素就是右子树的后序遍历，剩下的为左子树的后序遍历。

分别知道左右子树的后序和中序后，需要构建左右子树，构建左右子树就是重复上述步骤，也就是一个递归实现。

**边界条件**：只要中序和后序遍历为空了，就表示没有节点了，返回 `null`。

##### Java 代码实现 #####

/**
     * 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 {
        
    
        private Map<Integer, Integer> inorderIndexMap = new HashMap<>();
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
        
            for(int i = 0; i < inorder.length; i++){
        
                inorderIndexMap.put(inorder[i], i);
            }
            return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
        }
    
        private TreeNode build(int[] inorder, int il, int ir, int[] postorder, int pl, int pr) {
        
            // 边界条件
            if(il > ir){
        
                return null;
            }
    
            int rootValue = postorder[pr];
            TreeNode root = new TreeNode(rootValue);
    
            int rootInorderIndex = inorderIndexMap.get(rootValue);
    
            // 右子树的中序遍历位置为 rootInorderIndex + 1 到 ir, 
    
            // 右子树节点个数
            int m = ir - rootInorderIndex;
    
            // 右子树的后序遍历位置为 pr - m 到 pr - 1
    
    
            root.right = build(inorder, rootInorderIndex + 1, ir, postorder, pr - m, pr - 1);
    
            // 左子树的中序遍历位置为 il 到 rootInorderIndex - 1, 
    
            // 左子树的后序遍历位置为 pl 到 pr - m - 1
    
            root.left = build(inorder, il, rootInorderIndex - 1, postorder, pl, pr - m - 1);
    
            return root;
    
        }
    }

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func buildTree(inorder []int, postorder []int) *TreeNode {
        
        inorderIndexMap := make(map[int]int, 0)
        for i := 0; i < len(inorder); i++ {
        
            inorderIndexMap[inorder[i]] = i
        }
    
        var build func(il int, ir int, pl int, pr int) *TreeNode
    
        build = func(il int, ir int, pl int, pr int) *TreeNode {
        
            if il > ir {
        
                return nil
            }
    
            rootVal := postorder[pr]
            rootInorderIndex := inorderIndexMap[rootVal]
    
            root := &TreeNode{
        Val : rootVal}
    
            // 右子树 中序 rootInorderIndex + 1 到 ir
            // 左子树 中序 il 到 rootInorderIndex - 1
    
            // 右子树 节点数
            m := ir - rootInorderIndex
    
            // 右子树 后序 pr - m 到 pr - 1
            // 左子树 后序 pl 到 pr - m - 1
    
            root.Left = build(il, rootInorderIndex - 1, pl, pr - m - 1)
            root.Right = build(rootInorderIndex + 1, ir, pr - m, pr - 1)
    
            return root
        }
    
        return build(0, len(inorder) - 1, 0, len(postorder) - 1)
    }

##### 复杂度分析 #####

**时间复杂度**： O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，构建 `inorderIndexMap` 的时间复杂度为  O ( N ) O(N) O(N)，递归函数每个节点都会被当作根节点计算一次，时间复杂度也是  O ( N ) O(N) O(N)。所以总体时间复杂度还是  O ( N ) O(N) O(N)。

**空间复杂度**：  O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，其中 `inorderIndexMap` 的空间复杂度为  O ( N ) O(N) O(N)，递归函数调用栈的最大深度也是 `N`，所以整体空间复杂度也是  O ( N ) O(N) O(N)。

[19848d2b2c23de23ac77f3a00cadbd6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b2689acdc80045d6a4a245cc2008969b.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzU1OTYwMjk1OQ==&mid=2247488202&idx=1&sn=a112500e1167cdbac8aba0a36ea939f9&chksm=fc159eaacb6217bc743dc4d76208760d2857ec89f3c394683aa91e0d4cdd14cd0dd34bf8d294#rd
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/bb9e424a03264ff0bdd0ef2861210b9a.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b0ac271dfcec4a838244d07afaf23d46.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/269a985e436a433bb36c9ff3f95b757b.png