您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
二叉树的最大深度(图文)
第十三双眼睛2023-11-26【数据结构与算法】人已围观
简介二叉树的最大深度
给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
思路:如果根节点为null,则返回0,如果根节点不为null,则递归左子树与右子树,最终将左子树的深度和右子树的深度取最大值然后加1即可。代码如下:
思路2:依次遍历树的每一层,定义一个变量来记录树的深度,创建一个队列,将队列的头节点放入队列,开始循环,将队列中的元素取出,如果它的左子节点不为null,就将左子节点放入队列,如果右子节点不为null,将右子节点也放入队列,遍历完本层以后,深度变量加1,如此循环,将队列中的每个元素取出,再次看各自的左子节点和右子节点是否存在,最终将记录数深度的变量返回即可。代码如下:
public static int method1(TreeNode root) { if (root == null) { return 0; } return Math.max(method1(root.left),method1(root.right)) + 1; } |
思路2:依次遍历树的每一层,定义一个变量来记录树的深度,创建一个队列,将队列的头节点放入队列,开始循环,将队列中的元素取出,如果它的左子节点不为null,就将左子节点放入队列,如果右子节点不为null,将右子节点也放入队列,遍历完本层以后,深度变量加1,如此循环,将队列中的每个元素取出,再次看各自的左子节点和右子节点是否存在,最终将记录数深度的变量返回即可。代码如下:
public static int method2(TreeNode root) { if (root == null) { return 0; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); int res = 0; while (!queue.isEmpty()) { 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 --; } res ++; } return res; } |
Tags:
很赞哦! ()
上一篇:对称二叉树(图文)