LeetCode：105. Construct Binary Tree from Preorder and Inorder Traversal（根据前序和中序还原二叉树）

╰+攻爆jí腚メ 2022-04-03 15:44 173阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

### 题目描述 ###

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

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

例如，给出

前序遍历 preorder = \[3,9,20,15,7\]  
中序遍历 inorder = \[9,3,15,20,7\]  
返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

来源：力扣（LeetCode）

--------------------

### java实现方法1： ###

/**
         * 构建二叉树
         *
         * @param preorder 前序数组
         * @param inorder  中序数组
         * @return 根节点
         */
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return helper(0, 0, inorder.length - 1, preorder, inorder);
        }
    
        /**
         * 还原二叉树帮助类
         *
         * @param preStart 前序开始位置
         * @param inStart  中序开始位置
         * @param inEnd    中序结束位置
         * @param preorder 前序数组
         * @param inorder  中序数组
         * @return 根节点
         */
        public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
            if (preStart > preorder.length - 1 || inStart > inEnd) {
                return null;
            }
            TreeNode root = new TreeNode(preorder[preStart]);
            int inIndex = 0;
            for (int i = inStart; i <= inEnd; i++) {
                if (inorder[i] == root.val) {
                    inIndex = i;
                }
            }
            root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
            root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
            return root;
        }

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode