通过前序与中序遍历序列构造二叉树

傷城~ 2023-03-14 05:30 82阅读 0赞

### 题目： ###

根据一棵树的前序遍历与中序遍历构造二叉树。  
**注意：**  
你可以假设树中没有重复的元素。  
例如，给出：

前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：  
![在这里插入图片描述][20200516031936915.png]

### 思路： ###

先序遍历的顺序是 Root -> Left -> Right，这就能方便的从根开始构造一棵树。  
首先，preorder 中的第一个元素一定是树的根，这个根又将 inorder 序列分成了左右两棵子树。现在我们只需要将先序遍历的数组中删除根元素，然后重复上面的过程处理左右两棵子树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 11]

### 代码： ###

贴上笔者的代码：

class Solution { 
        
        public TreeNode buildTree(int[] preorder, int[] inorder) { 
    
            if (preorder == null || inorder == null
                    || preorder.length == 0
                    || inorder.length == 0) { 
                return null;
            }
    
            List<Integer> preList = new ArrayList<>();
            for (int i = 0; i < preorder.length; i++) { 
                preList.add(preorder[i]);
            }
            return helper(preList, inorder);
        }
    
        private TreeNode helper(List<Integer> preList, int[] inorder) { 
    
            if (preList.size() == 0 || inorder == null || inorder.length == 0) return null;
    
            int value = preList.get(0);
            preList.remove(0);
            TreeNode node = new TreeNode(value);
    
            int[] leftTree = null;
            int[] rightTree = null;
            for (int i = 0; i < inorder.length; i++) { 
                if (inorder[i] == value) { 
                    leftTree = i==0?null:Arrays.copyOfRange(inorder, 0, i);
                    rightTree = i==inorder.length-1?null:Arrays.copyOfRange(inorder, i+1, inorder.length);
                }
            }
    
            node.left = helper(preList, leftTree);
            node.right = helper(preList, rightTree);
    
            return node;
        }
    }

提交后获得通过：  
![在这里插入图片描述][20200516032412955.png]  
不过看起来击败的用户数量不多，还有很大的优化空间。

[20200516031936915.png]: /images/20230312/6933619444a54f1798d0d7e9186395d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70]: /images/20230312/1558553ad9e84840a8b37e51072aec74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 1]: /images/20230312/aaea82b2fd2a48f2bd66ecec8f7d835b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 2]: /images/20230312/8005bff507924e3d83b768c0050c8908.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 3]: /images/20230312/92e18e9429d94199bac601a8bcb994e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 4]: /images/20230312/0acf6e5b13e94d72982db4f11a0b8590.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 5]: /images/20230312/c9452b43ccbc4ba88f4b9988b940485d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 6]: /images/20230312/bbfb472bf446458d87c3615763936698.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 7]: /images/20230312/6d9b580d61bd40af92ab7b0a0d965f7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 8]: /images/20230312/9c3646e855c94f40abf9b577f3a28001.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 9]: /images/20230312/11bfcb2b43a943eaa6a0b2873cc9546d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 10]: /images/20230312/12d513c32b944826a5a9f753a756a4f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxOTgwOA_size_16_color_FFFFFF_t_70 11]: /images/20230312/3f092937afea48c6bef970eb5785bd28.png
[20200516032412955.png]: /images/20230312/b652907a845a42ee99955c55f5385f7b.png