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

àì夳堔傛蜴生んèń 2022-12-22 11:07 137阅读 0赞

# 题目来源 #

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

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

## 递归 ##

解决此问题的关键在于要很熟悉树的各种遍历次序代表的什么，最好能够将图画出来。本题解带你先进行中序遍历和后续遍历二叉树，然后再根据遍历结果将二叉树进行还原。

首先，来一棵树  
![在这里插入图片描述][20201119195044988.png_pic_center]  
然后再看树的遍历结果  
![在这里插入图片描述][20201119195109202.png_pic_center]  
根据中序和后序遍历结果还原二叉树  
中序遍历和后续遍历的特性  
首先来看题目给出的两个已知条件 中序遍历序列 和 后序遍历序列 根据这两种遍历的特性我们可以得出两个结论

*  在后序遍历序列中,最后一个元素为树的根节点
 *  在中序遍历序列中,根节点的左边为左子树，根节点的右边为右子树  
    ![在这里插入图片描述][20201119195142733.png_pic_center]  
    算法
 *  为了高效查找根节点元素在中序遍历数组中的下标，我们选择创建哈希表来存储中序序列，即建立一个（元素，下标）键值对的哈希表。
 *  定义递归函数 helper(in\_left, in\_right) 表示当前递归到中序序列中当前子树的左右边界，递归入口为helper(0, n - 1) ：
    
     *  如果 in\_left > in\_right，说明子树为空，返回空节点。
     *  选择后序遍历的最后一个节点作为根节点。
     *  利用哈希表 O(1)O(1) 查询当根节点在中序遍历中下标为 index。从 in\_left 到 index - 1 属于左子树，从 index + 1 到 in\_right 属于右子树。
     *  根据后序遍历逻辑，递归创建右子树 helper(index + 1, in\_right) 和左子树 helper(in\_left, index - 1)。注意这里有需要先创建右子树，再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。
        
         *  返回根节点 root。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]

class Solution {
        
        int post_idx;
        int[] postorder;
        int[] inorder;
        Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();
    
        public TreeNode helper(int in_left, int in_right) {
        
            // 如果这里没有节点构造二叉树了，就结束
            if (in_left > in_right) {
        
                return null;
            }
    
            // 选择 post_idx 位置的元素作为当前子树根节点
            int root_val = postorder[post_idx];
            TreeNode root = new TreeNode(root_val);
    
            // 根据 root 所在位置分成左右两棵子树
            int index = idx_map.get(root_val);
    
            // 下标减一
            post_idx--;
            // 构造右子树
            root.right = helper(index + 1, in_right);
            // 构造左子树
            root.left = helper(in_left, index - 1);
            return root;
        }
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
        
            this.postorder = postorder;
            this.inorder = inorder;
            // 从后序遍历的最后一个元素开始
            post_idx = postorder.length - 1;
    
            // 建立（元素，下标）键值对的哈希表
            int idx = 0;
            for (Integer val : inorder) {
        
                idx_map.put(val, idx++);
            }
            
            return helper(0, inorder.length - 1);
        }
    }

复杂度分析

*  时间复杂度：O(n)，其中 nn 是树中的节点个数。
 *  空间复杂度：O(n)。

[106.]: https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/88092698aa2f45eba8b3ec7be92f1a86.png
[20201119195044988.png_pic_center]: https://img-blog.csdnimg.cn/20201119195044988.png#pic_center
[20201119195109202.png_pic_center]: https://img-blog.csdnimg.cn/20201119195109202.png#pic_center
[20201119195142733.png_pic_center]: https://img-blog.csdnimg.cn/20201119195142733.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201119195429285.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70#pic_center