树的前序遍历与中序遍历构造二叉树和树的中序遍历与后序遍历构造二叉树

左手的ㄟ右手 2024-03-24 11:02 63阅读 0赞

**目录**

一.树的前序遍历与中序遍历构造二叉树

1.题目描述

2.问题分析

3.代码实现

二.树的中序遍历与后序遍历构造二叉树

1.题目描述

2.问题分析

3.代码实现

三.问题思考

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

## 一.树的前序遍历与中序遍历构造二叉树 ##

### 1.题目描述 ###

> 给定两个整数数组 `preorder` 和 `inorder` ，其中 `preorder` 是二叉树的**先序遍历**， `inorder` 是同一棵树的**中序遍历**，请构造二叉树并返回其根节点。

力扣:[力扣][Link 1]

### 2.问题分析 ###

我们根据 preorder = \[3,9,20,15,7\], inorder = \[9,3,15,20,7\]来分析如何手动构建一颗二叉树

① 首先根据前序遍历的特点,通过preorder我们可知3为根结点,再根据中序遍历的特点,通过inorder 我们可知3为根结点的左子树有\{9\},右子树有\{15,20,7\}这些元素

![dadd677eae2d4c87a4c843ebda91ef89.png][]

② 因为已经划分了左右子树,再看preorder,此时9为结点3左子树的根结点,20为结点3右子树的根结点,再看inorder ,此时左子树已经完成,结点20的左子树有\{15\},右子树有\{7\};

![64e8970e92d649a1a511507427d3d8c0.png][]

③ 因为已经划分了左右子树,再看preorder,此时15为结点20左子树的根结点,20为结点3右子树的根结点,,此时preorder数组已经遍历完毕,整棵树也已经构建完毕了

![8f86ccb2917948d3a787eeb04301bfd6.png][]

手动已经实现了二叉树的构建,其实关键一共就两步,**第一步是在前序遍历列表寻找根结点(也就是子树的第一个元素),第二步是在中序遍历寻找根结点的位置,根结点左边为左子树的结点范围,右边为右子树的结点范围.**

**接下来我们看代码实现(看代码实现的代码),代码递归实现和我们手动实现的顺序不一样,我们是同时寻找左右子树,递归是先构建根结点,然后构建左子树,最后构建右子树,直到全部遍历完成.(按照前序遍历(根左右)的方式)**

大致的顺序如下:没有一步步递归,只画出了关键的步骤

![4f4dc82e52674942bd2ee56ffb94842c.png][]

![6fbffe90110f4174832dd853cbbae5fa.png][]

![4905cf853e4b4682bbce9c547d0664d6.png][]

![53cc26a5b07d4702a0d36f5e47e8898d.png][]

其实不加 if(index==preorder.length)return null; 判断也没有错,只不过加上更加直观

### 3.代码实现 ###

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    
        public TreeNode buildTree(int[] preorder, int[] inorder) {
              for (int i = 0; i < inorder.length; ++i) {
                map.put(inorder[i], i);
            }
           return buildTreeHelper(preorder,inorder,0,inorder.length-1);
    
        }
        int index=0;
        public TreeNode buildTreeHelper(int[] preorder, int[] inorder,int left,int right){
            if(index==preorder.length){
                return null;
            }
            if(left>right){
                return null;
            }
            //1.前序数组的第一个为根结点
            int val=preorder[index++];
            TreeNode root=new TreeNode(val);
            //2.寻找中序遍历的左右子树的范围
            int mid=map.get(val);
            root.left=buildTreeHelper(preorder,inorder,left,mid-1);
            root.right=buildTreeHelper(preorder,inorder,mid+1,right);
            return root;
    
        }

## 二.树的中序遍历与后序遍历构造二叉树 ##

### 1.题目描述 ###

> 给定两个整数数组 `inorder` 和 `postorder` ，其中 `inorder` 是二叉树的中序遍历， `postorder` 是同一棵树的后序遍历，请你构造并返回这颗 *二叉树* 。

力扣:[力扣][Link 2]

### 2.问题分析 ###

我们根据 inorder = \[9,3,15,20,7\], postorder = \[9,15,7,20,3\]来分析如何手动构建一颗二叉树

树的中序遍历与后序遍历和前边那个构建二叉树还是有稍微的不同的,但是大体思路是一致的.

中序和后序需要根据后序遍历来选取根结点,根结点是子树结点范围中的最后一个,例如postorder = \[9,15,7,20,3\]的根结点是最后一个\{3\};并且代码实现index从后向前遍历,先构建的右子树

① 首先根据后序遍历的特点,通过postorder我们可知3为根结点,再根据中序遍历的特点,通过inorder 我们可知3为根结点的左子树有\{9\},右子树有\{15,20,7\}这些元素

![dadd677eae2d4c87a4c843ebda91ef89.png][]

② 因为已经划分了左右子树,再看postorder,此时9为结点3左子树的根结点,20为结点3右子树的根结点,再看inorder ,此时左子树已经完成,结点20的左子树有\{15\},右子树有\{7\};

![64e8970e92d649a1a511507427d3d8c0.png][]

③ 因为已经划分了左右子树,再看preorder,此时15为结点20左子树的根结点,20为结点3右子树的根结点,,此时preorder数组已经遍历完毕,整棵树也已经构建完毕了

![8f86ccb2917948d3a787eeb04301bfd6.png][]

由上面可以看出中序和后序构建二叉树和前序和中序构建二叉树的思路是一样的,实现也是一样的,代码递归构建却有很大的不同,**代码递归实现和我们手动实现的顺序不一样,我们是同时寻找左右子树,递归是构建根结点,然后构建好右子树,最后构建左子树,直到全部遍历完成.(按照中右左的方式)**

![ee75550335314922868c1d234567758b.png][]

![e07f5fd7045e47479b131093cfa32dce.png][] ![2ac62f87e71d4148bc610ab1e2109c73.png][]

![6997eca5ab1747a195c67af1b6c9ffea.png][]

其实不加 if(index==preorder.length)return null; 判断也没有错,只不过加上更加直观

### 3.代码实现 ###

Map<Integer, Integer> map = new HashMap<>();
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            for (int i = 0; i < inorder.length; ++i) {
                map.put(inorder[i], i);
            }
            index = postorder.length - 1;
            return findNode(inorder, postorder, 0, inorder.length - 1);
    
        }
    
        //这个index是postOrder的index
        int index;
    
        public TreeNode findNode(int[] inorder, int[] postorder, int left, int right) {
            if (index < 0) {
                return null;
            }
            if (left > right) {
                return null;
            }
            //1.从postorder找到根结点
            int val = postorder[index--];
            TreeNode root = new TreeNode(val);
            //2.从inorder找到左右子树
            Integer mid = map.get(val);
            //3.递归左子树
            root.right = findNode(inorder, postorder, mid+1, right);
            //4.递归右子树
            root.left = findNode(inorder, postorder, left, mid-1);
    
            return root;
    
        }

## 三.问题思考 ##

现在我们思考这样一个问题:我们是否可以根据前序和后序遍历的顺序,来构建一颗二叉树呢?

答案是不行的,我们观察前面两个题目可以知道:我们最关键的在于**寻找根结点,并找到它的左子树的结点范围和右子树结点范围**,但是根据前序和后序遍历,第一次我们可以找到根结点,但是我们无法判断它的左子树是哪些,右子树是哪些,因此无法根据这两种遍历方式构建一颗二叉树

[Link 1]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[dadd677eae2d4c87a4c843ebda91ef89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3fc95498963b4b23b79eb29223a1eeb0.png
[64e8970e92d649a1a511507427d3d8c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e2f3799b9dd34320a86d5ebb40505ebb.png
[8f86ccb2917948d3a787eeb04301bfd6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/80112f39b33e4169bed6375382194a6a.png
[4f4dc82e52674942bd2ee56ffb94842c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6f7aa2a6e659424da372bd820f6d139e.png
[6fbffe90110f4174832dd853cbbae5fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/48f01e306eb441fa9b8f2562297c1e27.png
[4905cf853e4b4682bbce9c547d0664d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ca26a9ed5dcb4d0f924070993d2435c8.png
[53cc26a5b07d4702a0d36f5e47e8898d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4d554b70e6ea496ca6b90bc9b8a738a8.png
[Link 2]: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
[ee75550335314922868c1d234567758b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/542aa0698f7e4878847c6c01b289b312.png
[e07f5fd7045e47479b131093cfa32dce.png]: https://img-blog.csdnimg.cn/e07f5fd7045e47479b131093cfa32dce.png
[2ac62f87e71d4148bc610ab1e2109c73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/fc97553e73414d37a5f1bd1752ca3916.png
[6997eca5ab1747a195c67af1b6c9ffea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9a86ef215ec940ada2e87410fbbcde83.png