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

￡神魔★判官ぃ 2023-10-16 09:38 42阅读 0赞

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

*  题干描述
 *  解题思路
 *  思考题
 *  代码实现
 *   *  方法一
     *  方法二

# 题干描述 #

[力扣入口-106.从中序与后序遍历序列构造二叉树][-106.]

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

注意: 你可以假设树中没有重复的元素。

例如，给出

*  中序遍历 inorder = \[9,3,15,20,7\]
 *  后序遍历 postorder = \[9,15,7,20,3\] 返回如下的二叉树：  
    ![在这里插入图片描述][3af21b7c3b9942e8b013b29d037950f1.png]

# 解题思路 #

首先回忆一下如何根据两个顺序构造一个唯一的二叉树，就是以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。

一层一层切下去，每次后序数组最后一个元素就是节点元素。

如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。

流程图：  
![在这里插入图片描述][348c046323d647189489c3fdf6cbcf01.png]  
那么代码应该如何写呢？说到一层一层切割，就应该想到了递归。

具体分步：

1.  如果数组大小为零的话，就说明是空节点了。
2.  如果不为空，那么取后序数组最后一个元素作为节点元素。
3.  找到后序数组最后一个元素再中序数组的位置，作为切割点。
4.  切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）。
5.  切割后序数组，切成后序左数组和后序右数组。
6.  递归处理左区间和右区间。

**难点大家应该发现了，就是如何切割，以及边界值找不好很容易乱套。**

此时应该注意确定切割的标准，是左闭右开，还有左开右闭，还是左闭右闭，这个就是不变量，要在递归中保持这个不变量。

**在切割的过程中会产生四个区间，把握不好不变量的话，一会左闭右开，一会左闭右闭，必然乱套！**

循环不变量非常重要，在二分查找以及螺旋矩阵的求解中，坚持循环不变量非常重要，本题也是。

首先要切割中序数组，为什么先切割中序数组呢？

切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组。

中序数组相对比较好切，找到切割点（后序数组的最后一个元素）在中序数组的位置，然后切割，如下代码中使用左闭右开的原则：

// 找到中序遍历的切割点
    int delimiterIndex;
    for(delimiterIndex = 0; delimiterIndex < inorder.size();delimiterIndex++){
        
    	if(inorder[delimiterIndex] == rootValue) break;
    }
    
    // 左闭右开区间: [0, delimiterIndex)
    vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
    // [delimiterIndex + 1, end)
    vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());

接下来就要切割后序数组了。

首先后序数组的最后一个元素指定不能要了，这是切割点 也是 当前二叉树中间节点的元素，已经用了。

后序数组的切割点怎么找？

后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。

**此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。**

中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。

代码如下：

// postorder舍弃末尾元素，因为这个元素就是中间节点，已经用过了
    postorder.resize(postorder.size() - 1);
    
    // 左闭右开，注意这里使用了左中序数组大小作为切割点:[0, leftInorder.size)
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
    // [leftInorder.size(), end)
    vector<int> rightPostOrder(postorder.begin(), leftInorder.size(), postorder.end());

此时，中序数组切成了左中序数组和右中序数组，后序数组切割成左后序数组和右后序数组。

# 思考题 #

前序和中序可以唯一确定一颗二叉树，后序和中序可以唯一确定一颗二叉树。

那么前序和后序可以唯一确定一颗二叉树吗？  
**前序和后序不能唯一确定一颗二叉树**！因为没有中序遍历无法确定左右部分，也就是无法分隔。

# 代码实现 #

## 方法一 ##

// 106.从中序与后序遍历序列构造二叉树
    Map<Integer, Integer> map; // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder){
        
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
         // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length); // 前闭后开
    }
    
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd){
        
        // 参数里的范围都是前闭后开
        if(inBegin >= inEnd || postBegin >= postEnd){
         // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
        int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
    
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }

## 方法二 ##

public TreeNode buildTree2(int[] inorder, int[] postorder){
        
        if(postorder.length == 0 || inorder.length == 0)
            return null;
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
        
        if(postorderStart == postorderEnd)
            return null;
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex;
        for(middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++){
        
            if(inorder[middleIndex] == rootVal){
        
                break;
            }
        }
    
        int leftInorderStart = inorderStart;
        int leftInorderEnd = middleIndex;
        int rightInorderStart = middleIndex + 1;
        int rightInorderEnd = inorderEnd;
    
        int leftPostorderStart = postorderStart;
        int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);
        int rightPostorderStart = leftPostorderEnd;
        int rightPostorderEnd = postorderEnd - 1;
        root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd,  postorder, leftPostorderStart, leftPostorderEnd);
        root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);
    
        return root;
    }

**参考资料**：[106.从中序与后序遍历序列构造二叉树][106.]

[-106.]: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[3af21b7c3b9942e8b013b29d037950f1.png]: https://img-blog.csdnimg.cn/3af21b7c3b9942e8b013b29d037950f1.png
[348c046323d647189489c3fdf6cbcf01.png]: https://img-blog.csdnimg.cn/348c046323d647189489c3fdf6cbcf01.png
[106.]: https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE