Leetcode原题
思路
二叉树深度就是 跟节点到叶子节点的 最大距离 。即根节点到最远叶子节点的最长路径上的节点数。
方法一 递归
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套哦~
