​

一、　二叉树的遍历 

一 、KY11  二叉树遍历

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：
输入包括1行字符串，长度不超过100。

输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

思路：先定义叶子节点，然后遍历字符串进行建树，遍历过程中如果遇到 ‘ #’ ，则进行 ｉ＋＋　跳过，如果遇到字符，则判断他的左右子树，进行递归

import java.util.Scanner;
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 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
           String str = in.nextLine();
           TreeNode root = buildTree(str);
           inOrder(root);
        }
    }
  private static int i = 0;
  private static TreeNode buildTree(String str){
      TreeNode root = null;
      if(str.charAt(i)!='#'){
         root = new TreeNode(str.charAt(i));
         i++;
         root.left = buildTree(str);
         root.right = buildTree(str);
      }else{
          i++;
      }
     return root;
  }
   private static void inOrder(TreeNode root){
       if(root  == null){
           return;
       }
       inOrder(root.left);
       System.out.print(root.val+" ");
       inOrder(root.right);
   }
}

 二、二叉树的层序遍历

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]

]

BM26 求二叉树的层序遍历

提示:

0 <= 二叉树的结点数 <= 1500

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        if(root == null)
            return res; 
        Queue<TreeNode> q = new LinkedList<TreeNode>(); 
        q.add(root);
        while(!q.isEmpty()){
            ArrayList<Integer> row = new ArrayList<>();  
            int n = q.size();
            for(int i = 0; i < n; i++){
                TreeNode cur = q.poll();
                row.add(cur.val);
 
                if(cur.left != null)
                    q.add(cur.left);
                if(cur.right != null)
                    q.add(cur.right);
            }
            res.add(row); 
        }
        return res;
    }
}

三、判断是否为完全二叉树

描述
给定一个二叉树，确定他是否是一个完全二叉树。

完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）

数据范围：节点数满足1≤n≤100

BM35 判断是不是完全二叉树

public boolean isCompleteTree (TreeNode root) {
      if(root == null){
        return false;
      }
    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 cur2 = qu.poll();
        if(cur2 != null){
          return false;
        }
      }
      return true;
    }

 

​