您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

二叉树的最大深度(图文)

第十三双眼睛2023-11-26【数据结构与算法】人已围观

简介二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

思路：如果根节点为null，则返回0，如果根节点不为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：

很赞哦！ ()

上一篇：对称二叉树(图文)

下一篇：将有序数组转换为二叉搜索树(图文)