leetcode刷题（9）二叉树（3）

ゝ一纸荒年。 2023-09-26 23:17 116阅读 0赞

各位朋友们，提前祝大家五一劳动节快乐啊！！！今天我为大家分享的是关于leetcode刷题二叉树相关的第三篇我文章，让我们一起来看看吧。

#### 文章目录 ####

*  1.二叉树的层序遍历
 *   *  题目要求
     *  做题思路
     *  代码实现
 *  2.从前序与中序遍历序列构造二叉树
 *   *  题目要求
     *  做题思路
     *  代码实现
 *  3.从中序与后序遍历序列构造二叉树
 *   *  题目要求
     *  做题思路
     *  代码实现

## 1.二叉树的层序遍历 ##

[leetcode之二叉树的层序遍历（难度：中等）][leetcode]

### 题目要求 ###

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例1  
![在这里插入图片描述][9a92d89c99ba4ac2afa4bab58f47bd56.png]  
输入：root = \[3,9,20,null,null,15,7\]  
输出：\[\[3\],\[9,20\],\[15,7\]\]

示例2  
输入：root = \[1\]  
输出：\[\[1\]\]

示例3  
输入：root = \[\]  
输出：\[\]

### 做题思路 ###

这道题我们可以借助队列这个数据结构，首先先将根节点放进队列中，然后我们计算此时队列的大小，记录下来，这个数字其实就是各层根节点的个数。我们等会要弹出相同数量的元素，在弹出的同时我们需要将弹出的根节点放进List中，并且将次根节点的非空左树和右树插入队列中。我们举个例子。  
![在这里插入图片描述][bd74dbafc5a0473abf83d7dfa0bca9d4.png]

![在这里插入图片描述][fd7e220351e04771829d99e187a6d47a.png]

![在这里插入图片描述][a301c8bc21bf44259ddbc4a736ee9902.png]  
![在这里插入图片描述][57558864ac674c4cabb591c03c8f9f97.png]  
![在这里插入图片描述][010a9819823942818c7b906259ae487d.png]  
![在这里插入图片描述][30ba38a3e63e4469827dd6f58a560c51.png]  
最后我们返回List就是我们需要的结果。

### 代码实现 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> list = new ArrayList<>();
            //当根节点为null时，我们直接返回list，这里list也为null
            if(root == null) {
        
                return list;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()) {
        
                int size = queue.size();
                List<Integer> tmp = new ArrayList<>();
                while(size > 0) {
        
                    TreeNode cur = queue.poll();
                    tmp.add(cur.val);
                    if(cur.left != null) {
        
                        queue.offer(cur.left);
                    }
                    if(cur.right != null) {
        
                        queue.offer(cur.right);
                    }
                    size--;
                }
                list.add(tmp);
            }
            return list;
        }
    }

![在这里插入图片描述][ec1f95d71a7a4acf854479a0d364291a.png]

## 2.从前序与中序遍历序列构造二叉树 ##

[leetcode之从前序与中序遍历序列构造二叉树（难度：中等）][leetcode 1]

### 题目要求 ###

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

示例 1:  
![在这里插入图片描述][8a1af50892b943b79fc7bb160e997dce.png]

输入: preorder = \[3,9,20,15,7\], inorder = \[9,3,15,20,7\]  
输出: \[3,9,20,null,null,15,7\]

示例 2:

输入: preorder = \[-1\], inorder = \[-1\]  
输出: \[-1\]

### 做题思路 ###

我们通过二叉树的前序遍历序列来确定根节点，通过中序遍历来确定左右子树，我们直接来举一个例子。  
![在这里插入图片描述][f57b6ac28f464de596e88d6d43080291.png]  
![在这里插入图片描述][ae988dcc3d6f40f5ba96fbe5b852ee37.png]  
![在这里插入图片描述][84b516a0b9e446079be80afa512d9cb8.png]

用inBegin和inEnd来分别表示左右子树的范围，当表示左树时inEnd = index-1  
表示右树时inBegin = index+1  
![在这里插入图片描述][ae5773c045ca4f36ba8b50f0ab49c3cf.png]  
此时9的左树为null，说明3的左树的树叶是9，也就是说我们递归结束的条件是inBegin > inEnd  
![在这里插入图片描述][379298cafbd2411b8a52d6e30eeb438b.png]

![在这里插入图片描述][2be45ef526494a17ac782aa86765ce58.png]

### 代码实现 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
    //创建一个成员变量用来遍历前序遍历序列
        public int i = 0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
        //我们inBegin默认为0，inEnd默认数组的最后一个元素的下标
            return buildTreeChild(preorder,inorder,0,inorder.length-1);
        }
    
        public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin, int inEnd) {
        
        //递归结束的条件
            if(inBegin > inEnd) {
        
                return null;
            }
            TreeNode root = new TreeNode(preorder[i]);
            int index = findIndex(preorder[i],inorder,inBegin,inEnd);
            i++;
            root.left = buildTreeChild(preorder,inorder,inBegin,index-1);
            root.right = buildTreeChild(preorder,inorder,index+1,inEnd);
    
            return root;
        }
    
        public int findIndex(int key,int[] inorder,int inBegin,int inEnd) {
        
            for(int j = inBegin; j<= inEnd; j++) {
        
                if(key == inorder[j]) {
        
                    return j;
                }
            }
    
            return -1;
        }
    }

![在这里插入图片描述][c987badc7ebf47e0afa6f342de55cc0c.png]

## 3.从中序与后序遍历序列构造二叉树 ##

[leetcode之从中序与后序遍历序列构造二叉树（难度：中等）][leetcode 2]

### 题目要求 ###

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

示例 1:  
![在这里插入图片描述][399d3ee712b74bc185a648e800fb2bbf.png]

输入：inorder = \[9,3,15,20,7\], postorder = \[9,15,7,20,3\]  
输出：\[3,9,20,null,null,15,7\]

示例 2:

输入：inorder = \[-1\], postorder = \[-1\]  
输出：\[-1\]

### 做题思路 ###

这道题的思路其实和上面的那个题差不多的，唯一不同的是我们需要从后序遍历序列的后面开始遍历，并且上一个题是先构建左子树，而我们这个题需要先构建右子树，因为后序遍历的顺序是先左子树、再右子树、最后是根节点，我们是从后序遍历的最后面开始的，所以我们构建的顺序也是不一样的。我们就直接来看代码吧。

### 代码实现 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public int i = 0;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
        
            i = postorder.length-1;
            return buildTreeChild(inorder,postorder,0,postorder.length-1);
        }
    
        public TreeNode buildTreeChild(int[] inorder,int[] postorder,int inBegin,int inEnd) {
        
            if(inBegin > inEnd) {
        
                return null;
            }
            TreeNode root = new TreeNode(postorder[i]);
            int index = findIndex(postorder[i],inorder,inBegin,inEnd);
            i--;
            root.right = buildTreeChild(inorder,postorder,index+1,inEnd);
            root.left = buildTreeChild(inorder,postorder,inBegin,index-1);
    
            return root;
        }
    
        public int findIndex(int key, int[] inorder, int inBegin, int inEnd) {
        
            for(int j = inBegin; j <= inEnd; j++) {
        
                if(inorder[j] == key) {
        
                    return j;
                }
            }
            return -1;
        }
    }

![在这里插入图片描述][5cef0da7101a4ce290131e61650e80ed.png]

[leetcode]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[9a92d89c99ba4ac2afa4bab58f47bd56.png]: https://img-blog.csdnimg.cn/9a92d89c99ba4ac2afa4bab58f47bd56.png
[bd74dbafc5a0473abf83d7dfa0bca9d4.png]: https://img-blog.csdnimg.cn/bd74dbafc5a0473abf83d7dfa0bca9d4.png
[fd7e220351e04771829d99e187a6d47a.png]: https://img-blog.csdnimg.cn/fd7e220351e04771829d99e187a6d47a.png
[a301c8bc21bf44259ddbc4a736ee9902.png]: https://img-blog.csdnimg.cn/a301c8bc21bf44259ddbc4a736ee9902.png
[57558864ac674c4cabb591c03c8f9f97.png]: https://img-blog.csdnimg.cn/57558864ac674c4cabb591c03c8f9f97.png
[010a9819823942818c7b906259ae487d.png]: https://img-blog.csdnimg.cn/010a9819823942818c7b906259ae487d.png
[30ba38a3e63e4469827dd6f58a560c51.png]: https://img-blog.csdnimg.cn/30ba38a3e63e4469827dd6f58a560c51.png
[ec1f95d71a7a4acf854479a0d364291a.png]: https://img-blog.csdnimg.cn/ec1f95d71a7a4acf854479a0d364291a.png
[leetcode 1]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[8a1af50892b943b79fc7bb160e997dce.png]: https://img-blog.csdnimg.cn/8a1af50892b943b79fc7bb160e997dce.png
[f57b6ac28f464de596e88d6d43080291.png]: https://img-blog.csdnimg.cn/f57b6ac28f464de596e88d6d43080291.png
[ae988dcc3d6f40f5ba96fbe5b852ee37.png]: https://img-blog.csdnimg.cn/ae988dcc3d6f40f5ba96fbe5b852ee37.png
[84b516a0b9e446079be80afa512d9cb8.png]: https://img-blog.csdnimg.cn/84b516a0b9e446079be80afa512d9cb8.png
[ae5773c045ca4f36ba8b50f0ab49c3cf.png]: https://img-blog.csdnimg.cn/ae5773c045ca4f36ba8b50f0ab49c3cf.png
[379298cafbd2411b8a52d6e30eeb438b.png]: https://img-blog.csdnimg.cn/379298cafbd2411b8a52d6e30eeb438b.png
[2be45ef526494a17ac782aa86765ce58.png]: https://img-blog.csdnimg.cn/2be45ef526494a17ac782aa86765ce58.png
[c987badc7ebf47e0afa6f342de55cc0c.png]: https://img-blog.csdnimg.cn/c987badc7ebf47e0afa6f342de55cc0c.png
[leetcode 2]: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[399d3ee712b74bc185a648e800fb2bbf.png]: https://img-blog.csdnimg.cn/399d3ee712b74bc185a648e800fb2bbf.png
[5cef0da7101a4ce290131e61650e80ed.png]: https://img-blog.csdnimg.cn/5cef0da7101a4ce290131e61650e80ed.png