算法打卡Day20

“蒹葭苍苍，白露为霜，所谓伊人，在水一方。”这是撩动心弦的遇见；“这位妹妹，我曾经见过。”这是宝玉和黛玉之间，初次见面时欢喜的遇见；“幸会，今晚你好吗？”这是《罗马假日》里，安妮公主糊里糊涂的遇见；“遇到你之前，我没有想过结婚，遇到你之后，我结婚没有想过和别的人。”这是钱钟书和杨绛之间，决定一生的遇见。今天和你们遇见，让我们彼此之间，感受到更多的美好。

Leetcode原题

104. 二叉树的最大深度

思路

二叉树深度就是 跟节点到叶子节点的 最大距离 。即根节点到最远叶子节点的最长路径上的节点数。

方法一 递归

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

方法二 利用队列

利用队列，每次将队列中的节点取出来扩展，有左叶子树和右叶子树就添加入队列中。
这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行拓展，最后我们用一个变量来维护拓展的次数，该二叉树的最大深度即为ans.

public int maxDepth(TreeNode root){
        if (root ==null){
            return 0;
        }
        Queue<TreeNode> queue= new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            /**
             * size用来记录本层级的结点是否处理完
             */
            int size= queue.size();
            while (size>0){
                TreeNode node= queue.poll(); //出队
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }

完整代码

import java.util.LinkedList;
import java.util.Queue;

/**
 * @PackageName: cn.study.sufa.Day19
 * @author: youjp
 * @create: 2022-05-06 22:09
 * @description: leecode 104 二叉树最大深度
 * @Version: 1.0
 */
public class Solution {

    public static void main(String[] args) {
        TreeNode node= new TreeNode(3);
        node.left=new TreeNode(9);
        node.right= new TreeNode(20);
        node.right.left =new TreeNode(15);
        node.right.right =new TreeNode(7);
        Solution s=new Solution();
        System.out.println(s.maxDepthWithQueue(node));
    }

    //方法一、递归 求跟节点到最远叶子节点最长路径上的节点数
/*    public int maxDepth(TreeNode root){
        if (root ==null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }*/

    //方法2.递归
    public int maxDepthWithQueue(TreeNode root){
        if (root ==null){
            return 0;
        }
        Queue<TreeNode> queue= new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            /**
             * size用来记录本层级的结点是否处理完
             */
            int size= queue.size();
            while (size>0){
                TreeNode node= queue.poll(); //出队
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }
}
class TreeNode{
    int val;
    TreeNode left ;
    TreeNode right;
    public TreeNode(){}

    public TreeNode(int val){
        this.val =val;
    }
    public TreeNode (int val,TreeNode left,TreeNode right){
        this.val =val;
        this.left= left;
        this.right =right;
    }
}

有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~