Leetcode刷题之路(101-110)

102.二叉树的层次遍历

二叉树的层次遍历题目链接

• 用bfs思想迭代

List<List<Integer>>  results;
    public List<List<Integer>> levelOrder(TreeNode root) {
           results = new ArrayList<>();
           if(root==null){
               return results;
           }
           Queue<TreeNode> queue = new LinkedList<>();
           queue.offer(root);
           while(!queue.isEmpty()){
               int size = queue.size();
               List<Integer> list = new ArrayList<>();
               for(int i=0;i<size;i++){
                   TreeNode p = queue.poll();
                   list.add(p.val);
                   if(p.left!=null){
                       queue.offer(p.left);
                   }
                   if(p.right!=null){
                       queue.offer(p.right);
                   }
               }
               results.add(list);
           }
           return results;
    }

104.二叉树的最大深度

二叉树的最大深度题目链接

• 方法一：用递归左右两边取最大，不为空的就加1，为空返回0

public int maxDepth(TreeNode root) {
         if(root==null){
             return 0;
         }
         return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
    }

• 方法二：用bfs的思想来迭代左右节点

 public int maxDepth(TreeNode root) {
         if(root==null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode p = queue.poll();
                if(p.left!=null){
                    queue.offer(p.left);
                }
                if(p.right!=null){
                    queue.offer(p.right);
                }
            }
            depth++;
        }
        return depth;
    }