[数据结构与算法]二叉树-学习

问题一：判定是否为完全二叉树

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Test2Tree {
    //判定一棵树是完全二叉树-->针对完全二叉树进行层序遍历，会出现两种阶段
    //①任何一个节点，一定有两个子树 当遇到某个节点只有左子树或没有子树的时候，(如果某个节点只有右子树肯定也不是完全二叉树)
    //②任何一个节点一定没有子树，当层序遍历结束后，整个树一直满足上述要求，就是二叉树

    public boolean isComleteTree(TreeNode root){
        //针对这个树进行层序遍历
        if(root==null){
            return true;
        }
        //定义一个是否进入二阶段的标志变量
        boolean isSecondStage=false;

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            //取出队首元素
            TreeNode cur=queue.poll();

            //针对当前节点进行访问（判断是否符合完全二叉树的要求）
            if(!isSecondStage){
                //进入第一阶段

                if(cur.left!=null&&cur.right!=null){
                    //直接把这两个子树入队列
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }else if (cur.left==null&&cur.right!=null){
                    //当前第一阶段某节点只有右子树，不是完全二叉树
                    return false;
                }else if(cur.left!=null&&cur.right==null){
                    //切换第二阶段
                    isSecondStage=true;
                    queue.offer(cur.left);
                }else {
                    //左右子树都为空，也切换到第二阶段
                    isSecondStage=true;
                }
            }else {
                //这是第二阶段
                //任何一个节点必须没有子树
                //只要找到某节点带子树，是反例
                if(cur.left!=null||cur.right!=null){
                    return false;
                }
            }
        }
        //整个树都遍历完也无反例
        return true;
    }
}

问题二：读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树

public class BuildTreeDemo {
    static class TreeNode{
        public int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        //使用循环 多组输入测试数据
        while (scanner.hasNext()){
            String line=scanner.next();
            //line这个字符串对应一组输入的二叉树数据值

            TreeNode root=build(line);
            inOder(root);
            System.out.println();
        }
    }

    private static int index=0;

    private static TreeNode build(String line){
        //为了在后面的递归创建过程中能时刻知道当前访问到line中的哪个元素
        //使用一个专门变量index记录
        //通过下面的方法辅助完成递归
        index=0;
        return createTreePreOder(line);
    }

    private static TreeNode createTreePreOder(String line){
        //获取到当前处理到哪个节点

        char cur=line.charAt(index);
        if(cur=='#'){
            return null;
        }
        //当前字符不是#就创建一个节点
        TreeNode root=new TreeNode(cur);
        index++;
        //准备处理下一个节点
        //当前root左子树先序遍历
        root.left=createTreePreOder(line);

        index++;
        root.right=createTreePreOder(line);

        return root;
    }
    //中序遍历
    public  static void inOder(TreeNode root){
        if(root==null){
            return;
        }
        inOder(root.left);
        System.out.print(root.val+" ");
        inOder(root.right);
    }

问题三：一个二叉树，返回其按层序遍历得到的节点值

//一个二叉树，请你返回其按层序遍历得到的节点值

    //result是一个二维数组
    static List<List<Integer>> result=new ArrayList<>();
    public  List<List<Integer>> levelOder(TreeNode root){
        if(root==null){
            return result;
        }

        //helper方法辅助递归，第二个参数表示当前的层数，层数从0开始计算，和list下标正好一致
        helper(root,0);
        return result;
    }

    private void helper(TreeNode root,int level){
        if(level==result.size()){
            result.add(new ArrayList<>());
        }

        //把当前节点添加到result中的合适位置
        result.get(level).add(root.val);
        /*List<Integer> row=result.get(level);
        row.add(root.val)*/;
        if(root.left!=null){
            helper(root.left,level+1);
        }

        if(root.right!=null){
            helper(root.right,level+1);
        }
    }