[Leetcode][第889题][JAVA][根据前序和后序遍历构造二叉树][分治][递归]

系统管理员 2022-12-10 10:05 162阅读 0赞

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

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

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

**copyOfRange**

class Solution { 
        public TreeNode constructFromPrePost(int[] pre, int[] post) { 
            if(pre==null || pre.length==0) { 
                return null;
            }
            return dfs(pre,post);
        }
    	
        private TreeNode dfs(int[] pre,int[] post) { 
            if(pre==null || pre.length==0) { 
                return null;
            }
            //数组长度为1时，直接返回即可
            if(pre.length==1) { 
                return new TreeNode(pre[0]);
            }
            //根据前序数组的第一个元素，创建根节点 
            TreeNode root = new TreeNode(pre[0]);
            int n = pre.length;
            for(int i=0;i<post.length;++i) { 
                if(pre[1]==post[i]) { 
                    //根据前序数组第二个元素，确定后序数组左子树范围
                    int left_count = i+1;
                    //拆分前序和后序数组，分成四份
                    int[] pre_left = Arrays.copyOfRange(pre,1,left_count+1);
                    int[] pre_right = Arrays.copyOfRange(pre,left_count+1,n);
                    int[] post_left = Arrays.copyOfRange(post,0,left_count);
                    int[] post_right = Arrays.copyOfRange(post,left_count,n-1);
                    //递归执行前序数组左边、后序数组左边
                    root.left = dfs(pre_left,post_left);
                    //递归执行前序数组右边、后序数组右边
                    root.right = dfs(pre_right,post_right);
                    break;
                }
            }
            //返回根节点
            return root;
        }
    }	
    
    作者：wang_ni_ma
    链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/solution/tu-jie-889-gen-ju-qian-xu-he-hou-xu-bian-li-gou-2/

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

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

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

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

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d21b47c447f743169046f5ea4342b0c6.png
[Leetcode_889_JAVA]: https://blog.csdn.net/dadongwudi/article/details/108794248
[Leedcode_JAVA_105]: https://blog.csdn.net/dadongwudi/article/details/106278479