牛客网刷题——二叉树

╰半夏微凉° 2023-10-10 15:07 10阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> **文章目录**

1.KY11 二叉树遍历

2.二叉树的层序遍历

3.判断一棵树是否是完全二叉树

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

## 1.KY11 二叉树遍历 ##

[OJ链接][OJ]

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

思路：告诉了前序遍历，并且有空格，因此能根据示例构造出一棵二叉树，再进行中序遍历

![6d1f11ada1df4a408df78a60b9db413d.png][]

代码

import java.util.Scanner;
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            while (in.hasNextLine()) {
                String str = in.nextLine();
                TreeNode root = createTree(str);
                inOder(root);
            }
        }
        private static void inOder(TreeNode root){
            if(root == null){
                return;
            }
            inOder(root.left);
            System.out.print(root.val+" ");
            inOder(root.right);
        } 
        private 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;
        }
    }

![b17df04f3d6741f285589373d487fef2.png][]

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

> 给你二叉树的根节点 `root` ，返回其节点值的 **层序遍历** 。 （即逐层地，从左到右访问所有节点）
> 
> ![8ae80c30e80f484fa5931dee624fe475.png][]

思路：使用队列，迭代解决

定义一个list，当是空树时直接返回list。若不是空树，定义一个队列，根节点首先入队，当队列不为空时，定义一个size记录队列的元素个数，弹出队列的元素直到size=0，用tmp 接收弹出元素，这相当于用tmp记录了这一层的元素，所记录的tmp加入到list中。size为0后，这一层元素都被弹出并记录，如果队列当前节点左右子树不为空时，继续入队进行迭代，直到遍历完毕。最后将每list返回

代码

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            if(root == null){
                return list;
            }
            Queue<TreeNode> qu = new LinkedList<>();
            qu.offer(root);
            while(!qu.isEmpty()){
                int size = qu.size();
                List<Integer> tmp = new ArrayList<>();
                
                while(size>0){
                    TreeNode cur = qu.poll();
                    size--;
                    tmp.add(cur.val);
                    if(cur.left != null){
                        qu.offer(cur.left);
                    }
                    if(cur.right != null){
                        qu.offer(cur.right);
                    }
                }
                list.add(tmp);
            }
            return list;
        }
    }

时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)

空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)

## 3.判断一棵树是否是完全二叉树 ##

> 思路：用层序遍历，当队列中弹出空时检查队列剩下的元素是否还有非空值，若有，则不是完全二叉树

代码

public  boolean isCompleteTree(TreeNode root){
            if(root == null){
                return true;
            }
            Queue<TreeNode> qu = new LinkedList<>();
            qu.offer(root);
            while(!qu.isEmpty()){
                TreeNode cur = qu.poll();
                if(cur != null){
                    qu.offer(cur.left);
                    qu.offer(cur.right);
                }
                else{
                    break;
                }
            }
            while(!qu.isEmpty()){
                TreeNode pop = qu.poll();
                if(pop != null){
                    return false;
                }
            }
            return true;
        }

测试

System.out.println(testBianryTree.isCompleteTree(root));

![90babc9af52e43adb5b9fc35070f5aa4.png][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[OJ]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
[9fabc5c759d641d587467356ee99830c.png]: https://img-blog.csdnimg.cn/9fabc5c759d641d587467356ee99830c.png
[6d1f11ada1df4a408df78a60b9db413d.png]: https://img-blog.csdnimg.cn/6d1f11ada1df4a408df78a60b9db413d.png
[b17df04f3d6741f285589373d487fef2.png]: https://img-blog.csdnimg.cn/b17df04f3d6741f285589373d487fef2.png
[8ae80c30e80f484fa5931dee624fe475.png]: https://img-blog.csdnimg.cn/8ae80c30e80f484fa5931dee624fe475.png
[90babc9af52e43adb5b9fc35070f5aa4.png]: https://img-blog.csdnimg.cn/90babc9af52e43adb5b9fc35070f5aa4.png