[Leetcode][第106题][JAVA][ 从中序与后序遍历序列构造二叉树][分治][递归]

偏执的太偏执、 2022-12-10 08:56 110阅读 0赞

#### 【问题描述】\[中等\] ####

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

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

public class Solution { 
    
        public TreeNode buildTree(int[] inorder, int[] postorder) { 
            int inLen = inorder.length;
            int postLen = postorder.length;
            // 特判
            if (inLen != postLen) { 
                throw new RuntimeException("输入错误");
            }
            return buildTree(inorder, 0, inLen - 1, postorder, 0, postLen - 1);
        }
    
        /** * 使用中序遍历序列 inorder 的子区间 [inLeft, inRight] * 与后序遍历序列 postorder 的子区间 [postLeft, postRight] 构建二叉树 * * @param inorder 中序遍历序列 * @param inLeft 中序遍历序列的左边界 * @param inRight 中序遍历序列的右边界 * @param postorder 后序遍历序列 * @param postLeft 后序遍历序列的左边界 * @param postRight 后序遍历序列的右边界 * @return 二叉树的根结点 */
        private TreeNode buildTree(int[] inorder, int inLeft, int inRight,
                                   int[] postorder, int postLeft, int postRight) { 
            if (inLeft > inRight || postLeft > postRight) { 
                return null;
            }
    
            int pivot = postorder[postRight];
            int pivotIndex = inLeft;
    
            // 注意这里如果编写不当，有数组下标越界的风险
            while (inorder[pivotIndex] != pivot) { 
                pivotIndex++;
            }
            TreeNode root = new TreeNode(pivot);
            root.left = buildTree(inorder, inLeft, pivotIndex - 1,
                    postorder, postLeft, postRight - inRight + pivotIndex - 1);
    
            root.right = buildTree(inorder, pivotIndex + 1, inRight,
                    postorder, postRight - inRight + pivotIndex, postRight - 1);
            return root;
        }
    }
    
    作者：liweiwei1419
    链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/hou-xu-bian-li-python-dai-ma-java-dai-ma-by-liwe-2/

**HashMap优化**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]

class Solution { 
    
        HashMap<Integer,Integer> memo = new HashMap<>();
        int[] post;
    
        public TreeNode buildTree(int[] inorder, int[] postorder) { 
            for(int i = 0;i < inorder.length; i++) memo.put(inorder[i], i);
            post = postorder;
            TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1);
            return root;
        }
    
        public TreeNode buildTree(int is, int ie, int ps, int pe) { 
            if(ie < is || pe < ps) return null;
    
            int root = post[pe];
            int ri = memo.get(root);
    
            TreeNode node = new TreeNode(root);
            node.left = buildTree(is, ri - 1, ps, ps + ri - is - 1);
            node.right = buildTree(ri + 1, ie, ps + ri - is, pe - 1);
            return node;
        }
    }
    
    作者：reals
    链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/tu-jie-gou-zao-er-cha-shu-wei-wan-dai-xu-by-user72/

**copyOfRange 左必右开**

class Solution { 
        public TreeNode buildTree(int[] inorder, int[] postorder) { 
            if(inorder==null || postorder==null) { 
                return null;
            }
            return helper(inorder,postorder);
        }
    
        private TreeNode helper(int[] in, int[] post) { 
            if(in.length==0) { 
                return null;
            }
            //根据后序数组的最后一个元素，创建根节点
            TreeNode root = new TreeNode(post[post.length-1]);
            //在中序数组中查找值等于【后序数组最后一个元素】的下标
            for(int i=0;i<in.length;++i) { 
                if(in[i]==post[post.length-1]) { 
                    //确定这个下标i后，将中序数组分成两部分，后序数组分成两部分
                    int[] inLeft = Arrays.copyOfRange(in,0,i);
                    int[] inRight = Arrays.copyOfRange(in,i+1,in.length);
                    int[] postLeft = Arrays.copyOfRange(post,0,i);
                    int[] postRight = Arrays.copyOfRange(post,i,post.length-1);
                    //递归处理中序数组左边，后序数组左边
                    root.left = helper(inLeft,postLeft);
                    //递归处理中序数组右边，后序数组右边
                    root.right = helper(inRight,postRight);
                    break;
                }
            }
            return root;
        }
    }
    
    作者：wang_ni_ma
    链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/liang-chong-shi-xian-dong-hua-yan-shi-106-cong-zho/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#### 【总结】 ####

###### 1.前中后序遍历变化的是\[中\]的位置，左到右的顺序不改变 ######

*  前序遍历 中左右
 *  中序遍历 左中右
 *  后续遍历 左右中

###### 2.还原二叉树 借助HashMap or copyOfRange ######

根据前序和后序遍历构造二叉树  
[\[Leetcode\]\[第889题\]\[JAVA\]\[根据前序和后序遍历构造二叉树\]\[分治\]\[递归\]][Leetcode_889_JAVA]  
前序+中序遍历可画出原二叉树  
[\[Leedcode\]\[JAVA\]\[第105题\]\[从前序与中序遍历序列构造二叉树\]\[栈\]\[递归\]\[二叉树\]][Leedcode_JAVA_105]  
后续+中序遍历可画出原二叉树  
[\[Leetcode\]\[第106题\]\[JAVA\]\[ 从中序与后序遍历序列构造二叉树\]\[分治\]\[递归\]][Leedcode_JAVA_105]

###### 3. 多画图 写写写 遍历代码 手撕变量 大脑保持清醒 ######

转载链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/hou-xu-bian-li-python-dai-ma-java-dai-ma-by-liwe-2/  
转载链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/tu-jie-gou-zao-er-cha-shu-wei-wan-dai-xu-by-user72/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/556edb8a9cfd4a8cac9cac5edb362ded.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/f3376583cfb641b6a1b89275e853b555.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/59b5ffd22d954bcfb0ad739e94212292.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/6a1f604dddf54f148e6db320fd77f98e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/99122aeff92143989840c03843659e51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/607479252ca44184be47f5a6d0fdf95e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/5f2464a1fadb4646bd48e17d0b0ca080.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/1bd8bbdbe3274fd19a854c791f036d8e.png
[Leetcode_889_JAVA]: https://blog.csdn.net/dadongwudi/article/details/108794248
[Leedcode_JAVA_105]: https://blog.csdn.net/dadongwudi/article/details/106278479