【每日练习】二叉树

我不是女神ヾ 2024-04-23 21:21 81阅读 0赞

> ⭐ 作者：小胡\_不糊涂  
> ? 作者主页：[小胡\_不糊涂的个人主页][Link 1]  
> ? 收录专栏：[二叉树][Link 2]  
> ? 持续更文，关注博主少走弯路，谢谢大家支持 ?

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

*  一、101. 对称二叉树
 *   *  1. 题目简介
     *  2. 代码
     *  3. 运行结果
 *  二、二叉树的遍历
 *   *  1. 题目简介
     *  2. 代码
 *  三、二叉树的分层遍历
 *   *  1. 题目简介
     *  2. 代码
     *  3. 运行结果

## 一、101. 对称二叉树 ##

### 1. 题目简介 ###

> 给你一个二叉树的根节点 root ，检查它是否轴对称。  
> ![在这里插入图片描述][3f546406b45f4b22990fe75c49222799.png]

### 2. 代码 ###

class Solution {
        
        //对称二叉树
        public boolean isSymmetric(TreeNode root) {
        
            if(root==null){
        
                return true;
            }
            return dfs(root.left,root.right);
        }
        public static boolean dfs(TreeNode left,TreeNode right){
        
            if(left==null&&right==null){
        
                return true;
            }
            if(left==null||right==null){
        
                return false;
            }
            if(left.val!=right.val){
        
                return false;
            }
            return dfs(left.left,right.right)&&dfs(left.right,right.left);
        }
    }

### 3. 运行结果 ###

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

## 二、二叉树的遍历 ##

### 1. 题目简介 ###

> 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC\#\#DE\#G\#\#F\#\#\# 其中“\#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。  
> 输入描述：  
> 输入包括1行字符串，长度不超过100。  
> 输出描述：  
> 可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。  
> ![在这里插入图片描述][29d9e770130949e8b5e10e4ba7aad081.png]

### 2. 代码 ###

//二叉树的遍历
    class TreeNode{
        
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
        
            this.val=val;
        }
    }
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            String str=in.nextLine();
            TreeNode root=createTree(str);
            inOrder(root);
    
        }
        public static int i=0;
        //建树
        public static TreeNode createTree(String str){
        
            TreeNode root=null;
            if(str.charAt(i)!='#'){
        
                root=new TreeNode(str.charAt(i));
                i++;
                root.left=createTree(str);
                root.right=createTree(str);
            }else{
        
                i++;
            }
            return root;
        }
        //中序遍历
        public static void inOrder(TreeNode root){
        
            if(root==null){
        
                return;
            }
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder((root.right));
        }
    }

## 三、二叉树的分层遍历 ##

### 1. 题目简介 ###

> 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。  
> ![在这里插入图片描述][347324db8acc4062befa5499ec4365c7.png]

### 2. 代码 ###

class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> ret=new ArrayList<List<Integer>>();
            if(root==null){
        
                return ret;
            }
            Queue<TreeNode> queue=new LinkedList<TreeNode>();//依照队列先进先出原则
            queue.offer(root);
            while(!queue.isEmpty()){
        
                List<Integer> level=new ArrayList<>();
                int length=queue.size();
                for(int i=1;i<=length;i++){
        
                    TreeNode node=queue.poll();
                    level.add(node.val);
                    if(node.left!=null){
        
                        queue.offer(node.left);
                    }
                    if(node.right!=null){
        
                        queue.offer(node.right);
                    }
                }
                ret.add(level);
            }
            return ret;
        }
    }

### 3. 运行结果 ###

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

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

来源：力扣（LeetCode），著作归力扣网络所有。  
如果本篇文章对你有所启发的话，希望可以多多支持作者，谢谢大家！

[Link 1]: https://blog.csdn.net/iLoyo_
[Link 2]: http://t.csdnimg.cn/wrQhX
[3f546406b45f4b22990fe75c49222799.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/46033b82cae94f8b8ba88cbbe4e906f1.png
[e934808728034d7e92221e12985b6245.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/aae0c6e87b8641708d9d4f8f85df86a6.png
[29d9e770130949e8b5e10e4ba7aad081.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c4949e00f4244885a8338a2671688a03.png
[347324db8acc4062befa5499ec4365c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c30d1ba18120471298a13aa1b9f312c6.png
[a557b5ac2a38490ea9279423bf898a69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/89d1a55f22204640acfb181ddcc8d428.png