leetcode刷题（7）二叉树（1）

淩亂°似流年 2023-09-26 21:08 104阅读 0赞

哈喽大家好，这是我leetcode刷题的第七篇，这两天我将更新leetcode上关于二叉树方面的题目，如果大家对这方面感兴趣的话，欢迎大家持续关注，谢谢大家。  
那么我们就进入今天的主题。

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

*  1.二叉树的前序遍历
 *   *  题目要求
     *  示例
     *  做题思路
     *  代码实现
 *  2.二叉树的中序遍历
 *   *  做题思路
     *  代码实现
 *  3.二叉树的后序遍历
 *   *  做题思路
     *  代码实现
 *  4.相同的树
 *   *  题目要求
     *  示例
     *  做题思路
     *  代码实现
 *  5.另一颗树的子树
 *   *  题目要求
     *  示例
     *  做题思路
     *  代码实现

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

[leetcode之二叉树的前序遍历（难度：简单）][leetcode]

### 题目要求 ###

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

### 示例 ###

示例 1：  
![在这里插入图片描述][c504bd3097864384b0cde1b8e8171065.png]

输入：root = \[1,null,2,3\]  
输出：\[1,2,3\]

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

示例 3：

输入：root = \[1\]  
输出：\[1\]

示例 4：  
![在这里插入图片描述][3538f81c222e45ceab65dacca03e8616.png]

输入：root = \[1,2\]  
输出：\[1,2\]

示例 5：  
![在这里插入图片描述][4e9ff41d1c834dc5b74640b545ac8dc9.png]

输入：root = \[1,null,2\]  
输出：\[1,2\]

### 做题思路 ###

二叉树的遍历分为前序遍历、中序遍历和后序遍历，前序遍历是指先遍历根，在遍历左子树，最后遍历右子树。做二叉树相关的题目比较简单的思路一般就是使用递归，同样这题我们也使用递归来遍历二叉树。

![在这里插入图片描述][df67e1d74a1d4ba7971162e31a0859e5.png]  
list.add(root.val)  
![在这里插入图片描述][4a9c8132d716440f87c2461140b9e7b4.png]

![在这里插入图片描述][65c822c19f654e6cada08a19ed647e1c.png]  
![在这里插入图片描述][03364113c3d7467bb2b5f2ce864e0b5a.png]

![在这里插入图片描述][83f56f3688574fb19dd512792b60cc33.png]  
![在这里插入图片描述][a751ed92c4674d94a27774ba34f87689.png]

![在这里插入图片描述][ae7b13dc0e284b31ad28d288bd07c011.png]  
root为null时，返回null，结束当前的递归，执行之前递归的内容。  
![在这里插入图片描述][afa0e26377e14344a5326000d6cdad57.png]  
![在这里插入图片描述][577661281133422a85fa20bc57b961ac.png]  
![在这里插入图片描述][e0f7b7f804134646b370fa7d333d3cbc.png]  
![在这里插入图片描述][a73bdddae00848d08940338cc31460cf.png]![在这里插入图片描述][a777edeedb0c4837a073b13925400c34.png]

右子树是同一个道理  
![在这里插入图片描述][f1e189b50b01431c9dd9f190796d9f65.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 List<Integer> preorderTraversal(TreeNode root) {
        
        //因为题目要求我们返回List<Integer>类型，所以我们创建一个list
            List<Integer> list = new ArrayList<>();
            //递归结束的条件
            if(root == null) {
        
                return list;
            }
            //先遍历根结点
            list.add(root.val);
            //左子树
            List<Integer> leftTree = preorderTraversal(root.left);
            list.addAll(leftTree);
            //右子树
            List<Integer> rightTree = preorderTraversal(root.right);
            list.addAll(rightTree);
    
            return list;
        }
    }

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

## 2.二叉树的中序遍历 ##

[leetcode之二叉树的中序遍历（难度：简单）][leetcode 1]

### 做题思路 ###

二叉树的中序遍历跟二叉树的前序遍历思路是一样的，不同的只是遍历的顺序，中序遍历是先遍历左子树，然后是根节点，再就是右子树。

### 代码实现 ###

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

## 3.二叉树的后序遍历 ##

[leetcode之二叉树的后序遍历（难度：简单）][leetcode 2]

### 做题思路 ###

二叉树的后序遍历是先遍历左子树，然后是右子树，最后是根节点

### 代码实现 ###

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

## 4.相同的树 ##

[leetcode之相同的树（难度：简单）][leetcode 3]

### 题目要求 ###

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

### 示例 ###

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

输入：p = \[1,2,3\], q = \[1,2,3\]  
输出：true

### 做题思路 ###

这个题我们可以先判断两个树的结构是否相同，如果结构相同我们就判断对应位置的数据是否相同，我们判断的顺序是先判断根节点，然后是左子树，再是右子树。

### 代码实现 ###

/**
     * 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 boolean isSameTree(TreeNode p, TreeNode q) {
        
        //当q或者p其中有一个为null时，我们就需要判断两个树的结构是否相同
            if(p == null || q == null) {
        
            //都为null则表示结构相同
                if(p == null && q == null) {
        
                    return true;
                }else {
        
                    return false;
                }
            }
            //判断根结点的数据是否相同
            if(p.val != q.val) {
        
                return false;
            }
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
    }

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

## 5.另一颗树的子树 ##

[leetcode之另一棵树的子树（难度：简单）][leetcode 4]

### 题目要求 ###

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

### 示例 ###

![在这里插入图片描述][16f9876869aa418ea5e5232c17a087f0.png]  
输入：root = \[3,4,5,1,2\], subRoot = \[4,1,2\]  
输出：true

### 做题思路 ###

我们做这个题需要用到前面的判断两个树是否相等，我们判断root是否有跟subRoot这个树相同的子树。

### 代码实现 ###

/**
     * 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 boolean isSametree(TreeNode p,TreeNode q) {
        
            //判断结构是否相同
            if(p == null || q == null) {
        
                if(p == null && q == null) {
        
                    return true;
                }else {
        
                    return false;
                }
            }
            if(p.val != q.val) {
        
                return false;
            }
            return isSametree(p.left,q.left) && isSametree(p.right,q.right);
        }
    
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
        //当root遍历到空时说明root的左子树或者右子树中没有subRoot，返回fasle
            if(root == null) {
        
                return false;
            }
            //判断root整个树是否跟subRoot相同
            if(isSametree(root,subRoot)) {
        
                return true;
            }
            //判断左子树和右子树中是否含有subRoot
            return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
        }
    }

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

[leetcode]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[c504bd3097864384b0cde1b8e8171065.png]: https://img-blog.csdnimg.cn/c504bd3097864384b0cde1b8e8171065.png
[3538f81c222e45ceab65dacca03e8616.png]: https://img-blog.csdnimg.cn/3538f81c222e45ceab65dacca03e8616.png
[4e9ff41d1c834dc5b74640b545ac8dc9.png]: https://img-blog.csdnimg.cn/4e9ff41d1c834dc5b74640b545ac8dc9.png
[df67e1d74a1d4ba7971162e31a0859e5.png]: https://img-blog.csdnimg.cn/df67e1d74a1d4ba7971162e31a0859e5.png
[4a9c8132d716440f87c2461140b9e7b4.png]: https://img-blog.csdnimg.cn/4a9c8132d716440f87c2461140b9e7b4.png
[65c822c19f654e6cada08a19ed647e1c.png]: https://img-blog.csdnimg.cn/65c822c19f654e6cada08a19ed647e1c.png
[03364113c3d7467bb2b5f2ce864e0b5a.png]: https://img-blog.csdnimg.cn/03364113c3d7467bb2b5f2ce864e0b5a.png
[83f56f3688574fb19dd512792b60cc33.png]: https://img-blog.csdnimg.cn/83f56f3688574fb19dd512792b60cc33.png
[a751ed92c4674d94a27774ba34f87689.png]: https://img-blog.csdnimg.cn/a751ed92c4674d94a27774ba34f87689.png
[ae7b13dc0e284b31ad28d288bd07c011.png]: https://img-blog.csdnimg.cn/ae7b13dc0e284b31ad28d288bd07c011.png
[afa0e26377e14344a5326000d6cdad57.png]: https://img-blog.csdnimg.cn/afa0e26377e14344a5326000d6cdad57.png
[577661281133422a85fa20bc57b961ac.png]: https://img-blog.csdnimg.cn/577661281133422a85fa20bc57b961ac.png
[e0f7b7f804134646b370fa7d333d3cbc.png]: https://img-blog.csdnimg.cn/e0f7b7f804134646b370fa7d333d3cbc.png
[a73bdddae00848d08940338cc31460cf.png]: https://img-blog.csdnimg.cn/a73bdddae00848d08940338cc31460cf.png
[a777edeedb0c4837a073b13925400c34.png]: https://img-blog.csdnimg.cn/a777edeedb0c4837a073b13925400c34.png
[f1e189b50b01431c9dd9f190796d9f65.png]: https://img-blog.csdnimg.cn/f1e189b50b01431c9dd9f190796d9f65.png
[dca363b6ae7e4069bdec17399fd6835f.png]: https://img-blog.csdnimg.cn/dca363b6ae7e4069bdec17399fd6835f.png
[leetcode 1]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[7dd96164ed674bdc99daad98767dbe1a.png]: https://img-blog.csdnimg.cn/7dd96164ed674bdc99daad98767dbe1a.png
[leetcode 2]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[1454d28dbecf4eb99c46f50485a6eb8f.png]: https://img-blog.csdnimg.cn/1454d28dbecf4eb99c46f50485a6eb8f.png
[leetcode 3]: https://leetcode.cn/problems/same-tree/
[edc8aeb20db645ec8a0e832da6e1ffec.png]: https://img-blog.csdnimg.cn/edc8aeb20db645ec8a0e832da6e1ffec.png
[92d4ca82aa934890aedb5d50dd35aaa6.png]: https://img-blog.csdnimg.cn/92d4ca82aa934890aedb5d50dd35aaa6.png
[leetcode 4]: https://leetcode.cn/problems/subtree-of-another-tree/
[16f9876869aa418ea5e5232c17a087f0.png]: https://img-blog.csdnimg.cn/16f9876869aa418ea5e5232c17a087f0.png
[b898c30b8fb7426b8e124d517464688b.png]: https://img-blog.csdnimg.cn/b898c30b8fb7426b8e124d517464688b.png