代码随想录算法训练营day16

题目：104_二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

算法思想：

空间换时间，设置辅助数组count[]，下标表示层号。

前序遍历，deep记录深度 。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    int[] count = new int[10000];
 
    public int maxDepth(TreeNode root) {
        preorder(root, 1);
        int ans = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0)
                ans = i;
        }
        return ans;
 
    }
 
    public void preorder(TreeNode t, int deep) {
        if (t == null)
            return;
        count[deep]++;
        preorder(t.left, deep + 1);
        preorder(t.right, deep + 1);
    }
}

题目：n叉树的最大高度

给定一个 n 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如，给定一个 3叉树 :

我们应返回其最大深度，3。

算法思想：

1、采用层次遍历。

每一层的结点全部弹出队列时，deep++；用for循环限制同一层结点出队。

代码：

class Solution {
    public int maxDepth(Node root) {
        if(root==null) return 0;
        int deep = 0 ;
        //层次遍历
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            deep++;
            int size = queue.size();
            for(int j=0;j<size;j++){     //每一层的结点全部弹出队列deep++
                root = queue.poll();
                for (int i = 0; i < root.children.size(); i++) { 
                    if(root.children.get(i)!=null)
                        queue.offer(root.children.get(i));
                }
            }
        }
        return deep;
    }
}

算法思想：

题解的做法

2、计算型，后序遍历。

左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。

最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

代码：

public class Solution2 {
    public int minDepth(TreeNode root) {
        //计算型
        //注意：最小深度必须是到叶子结点的深度，不是到单亲结点的深度
        if(root==null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        //如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
        if(root.left==null&&root.right!=null)
            return right+1;
        //右子树为空，左子树不为空，最小深度是 1 + 左子树的深度
        else if(root.right==null&&root.left!=null)
            return left+1;
        //最后如果左右子树都不为空，返回左右子树深度最小值 + 1
        return Math.min(left,right)+1;
    }
}

题目：222_完全二叉树的结点个数

给出一个完全二叉树，求出该树的节点个数。

示例 1：

• 输入：root = [1,2,3,4,5,6]
• 输出：6

示例 2：

• 输入：root = []
• 输出：0

示例 3：

• 输入：root = [1]
• 输出：1

提示：

• 树中节点的数目范围是[0, 5 * 10^4]
• 0 <= Node.val <= 5 * 10^4
• 题目数据保证输入的树是 完全二叉树

算法思想：

没按题解写，按我自己的 操作型 。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    int count = 0;
    public int countNodes(TreeNode root) {
        preorder(root);
        return count;
    }
    
    public void preorder(TreeNode t){
        if(t==null) return ;
        count++;
        preorder(t.left);
        preorder(t.right);
 
    }
}