[数据结构与算法]【力扣刷题】Day16——二叉树专题

上一篇文章：【力扣刷题】Day15——二叉树专题_塔塔开!!!的博客-CSDN博客

6. 二叉树的最大深度

题目链接：104. - 力扣（LeetCode）

思路：dfs，前序遍历统计最大深度即可

static遇到的坑！！！

Code

 /**
    dfs：前序遍历求二叉树的最大深度
  */
class Solution {
    int res = -0x3f3f3f3f;
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        dfs(root, 0);
        return res;
    }
    public void dfs(TreeNode root, int depth){
        if(root == null){
            return ;
        }
        depth ++;
        res = Math.max(res, depth);
        dfs(root.left, depth);
        dfs(root.right, depth);
    }
}

8. 二叉树的最小深度

题目链接：111. 二叉树的最小深度 - 力扣（LeetCode）

二叉树的最小深度：当这个节点的左右儿子都为空时此时的深度才加入最小深度的比较计算！

思路：计算出所有满足条件的深度（左右儿子的深度）—— 当只有左右儿子都为空时才算的是能比较的深度，比较取最小即可（左子树的最小深度和右子树的最小深度比较）

Code

class Solution {
    int res = 0x3f3f3f3f;
    public int minDepth(TreeNode root) {
       if(root == null){
           return 0;
       }
        dfs(root, 0);
        return res;
    }
    public void dfs(TreeNode root, int depth){
        if(root == null){// 递归出口
            return ;
        }
        depth ++;
        if(root.left == null && root.right == null){
            res = Math.min(res, depth);
        }
        dfs(root.left,  depth);
        dfs(root.right,  depth);
    }
}

7. N 叉树的最大深度

题目链接：559. N 叉树的最大深度 - 力扣（LeetCode）

二叉树的最大深度扩展到N叉树，思路是一样的递归到最后一个节点然后比较，不同的是上一题是只有两棵子树，为此我们求出所有子树的最大深度然后比较即可。

Code

class Solution {
    int res = -0x3f3f3f3f;
    public int maxDepth(Node root) {
        if(root == null){
            return 0;
        }
        dfs(root, 0);
        return res;
    }
    public void dfs(Node root, int depth){
        if(root == null){
            return ;
        }
        // 遍历所有子树 求子树的最大深度（之前我们是只遍历左右子树）
        depth ++;
        res = Math.max(res, cnt);
        List<Node> C = root.children;
        for(Node child : C){
            dfs(child, cnt );
        }
    }
}

9. 完全二叉树的节点个数

题目链接：222. 完全二叉树的节点个数 - 力扣（LeetCode）222. 完全二叉树的节点个数 - 力扣（LeetCode）

解法一：BFS层序遍历统计节点数

Code

 // 思路一：直接BFS拿到所有节点
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        return bfs(root);
    }
    public int bfs(TreeNode root){
        List<TreeNode> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int len = q.size();
            for(int i = 0; i < len; i ++){
                TreeNode t = q.poll();
                list.add(t);
                if(t.left != null){
                    q.add(t.left);
                }
                if(t.right != null){
                    q.add(t.right);
                }
            }
        }
        return list.size();
    }
}

解法二：递归求解

求一棵完全二叉树的节点个数，其实就是递归遍历求左子树和右子树的个数，它们两个相加再加上根节点的个数 11，就是完全二叉树的节点数。

class Solution {
    public int countNodes(TreeNode root) {
        return dfs(root);
    }
    /**
        返回一个棵树的所有节点数
     */
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        return dfs(root.left) + dfs(root.right) + 1;
    }
}

解法三：dfs深度优先搜索统计节点数

// 思路三：直接dfs深度优先搜索统计即可
class Solution {
    int res = 0;// 开的全局变量！！！！！！
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        if(root == null){
            return ;
        }
        cnt ++;
        dfs(root.left);
        dfs(root.right);
    }
}