二叉树相关知识

1:二叉树的层序遍历->通过队列while实现

 class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
    
   List<List<Integer>> res = new ArrayList<List<Integer>>();
     if(root == null){
    
        return  res;
     }
    
     Queue<TreeNode> que = new LinkedList<TreeNode>();
     que.offer(root);
     while(!que.isEmpty()){
    
         List<Integer> level = new ArrayList<Integer>();
         int cursize = que.size();
         for(int i= 1;i<= cursize ;i++){
    
             TreeNode node = que.poll();
             level.add(node.val);
             if(node.left != null){
    
                 que.offer(node.left);
             }
             if(node.right != null){
    
                 que.offer(node.right);
             }
         }
         res.add(level);

     }
     return res;


}}

二叉树的层序遍历->递归实现

class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
    
        List<List<Integer>> res = new ArrayList<List<Integer>>();//存储最后结果
       

        level(root,0,res);

        return res;
    }
    public void level(TreeNode root,int level,List<List<Integer>> res){
    
        if(root == null){
    
            return ;
        }
        if(res.size() == level){
    
            List<Integer> list = new ArrayList<Integer>();
            list.add(root.val);
            res.add(list);

        }else{
    
            res.get(level).add(root.val);
        }
        level(root.left, level+1, res);
        level(root.right,level+1,res);
      

    }
   
}