【随想录】Day16—第六章 二叉树part03

题目1: 104. 二叉树的最大深度

• 题目链接：104. 二叉树的最大深度

1- 思路

• 利用层序遍历的方式，最大深度 即 二叉树的层数。

层序遍历

• 借助 Queue 队列实现

2- 题解

⭐二叉树的最大深度 ——题解思路

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int len = queue.size();
            while(len>0){
                TreeNode nowNode = queue.poll();
                if(nowNode.left!=null) queue.offer(nowNode.left);
                if(nowNode.right!=null) queue.offer(nowNode.right);
                len--;
            }
            res++;
        }
        return res;
    }
}

题目2: 559. N 叉树的最大深度

• 题目链接：559. N 叉树的最大深度

1- 思路

• 同理可以使用层序遍历的方式

2- 题解

⭐ N 叉树的最大深度 ——题解思路

class Solution {
    public int maxDepth(Node root) {
        if(root==null){
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int len = queue.size();
            while(len>0){
                Node nowNode = queue.poll();
                List<Node> forChild = nowNode.children;
                for(Node child:forChild){
                    queue.offer(child);
                }
                len--;
            }
            res++;
        }
        return res;
    }
}

题目3: 111. 二叉树的最小深度

• 题目链接：111. 二叉树的最小深度

1- 思路

• 利用层序遍历思想，遇到 左右 皆为空的结点，则结束层序遍历。

注意点

• 层序遍历需要单独写一个函数，遇到左右为 null 则返回，结束层序遍历
• 全局变量记录结果 ++ 的操作应该在 while 层序遍历判断前

2- 题解

⭐二叉树的最小深度 ——题解思路

class Solution {
    int res = 0;
    public int minDepth(TreeNode root) {
        levelTraversal(root);
        return res;
    }

    public void levelTraversal(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            res++;
            while(len>0){
                TreeNode nowNode = queue.poll();
                if(nowNode.left==null && nowNode.right==null) return ;

                if(nowNode.left!=null) queue.offer(nowNode.left);
                if(nowNode.right!=null) queue.offer(nowNode.right);
                len--;
            }
        }
    }
}

题目4: 222. 完全二叉树的节点个数

• 题目链接：222. 完全二叉树的节点个数

1- 思路

• 层序遍历，每次 poll 一个结点统计个数

2- 题解

⭐ 完全二叉树的节点个数 ——题解思路

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int len = queue.size();
            while(len>0){
                TreeNode nowNode = queue.poll();
                res++;
                if(nowNode.left!=null) queue.offer(nowNode.left);
                if(nowNode.right!=null) queue.offer(nowNode.right);
                len--;
            }
        }
        return res;
    }
}