首页 > 试题广场 >

二叉树的最大深度

[编程题]二叉树的最大深度

热度指数：148045 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

求给定二叉树的最大深度，

深度是指树的根节点到任一叶子节点路径上节点的数量。

最大深度是所有叶子节点的深度的最大值。

（注：叶子节点是指没有子节点的节点。）

数据范围： $0 \le n \le 100000$ ，树上每个节点的val满足 $|val| \le 100$
要求：空间复杂度 $O(1)$ ,时间复杂度 $O(n)$

示例1

输入

{1,2}

输出

示例2

输入

{1,2,3,4,#,#,5}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

Java

小飞快跑

通过遍历循环方式，将整个树问题拆分为左右单个更小的树即可

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

发表于 2024-09-13 11:45:47 回复(0)

Java

牛客348570162号

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

    // 层序遍历
    public int maxDepth (TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int res = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0;i<size;i++){
                TreeNode t = q.poll();
                if(t.left != null) q.add(t.left);
                if(t.right != null) q.add(t.right);
            }
            res++;
        }
        return res;
    }

发表于 2024-08-26 16:05:05 回复(0)

Java

人间水长东

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here

        // 调用递归序遍历解决二叉树最大深度问题
        return process(root);
    }

    // 递归序遍历二叉树函数 - 返回以root为根结点的子树的最大深度
    public int process(TreeNode root) {
        // 递归出口
        if (root == null) {
            // 当结点为空时，说明这一层的深度为0
            return 0;
        }
        
        // 记录左子树和右子树的最大深度
        int leftDepth = process(root.left);
        int rightDepth = process(root.right);

        // 返回左右子树最大深度的较大值，再加上本节点的1层深度
        return Math.max(leftDepth, rightDepth) + 1;
    }

}

发表于 2024-07-29 19:29:35 回复(0)

Java

牛客839384289号

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

发表于 2024-05-26 15:31:16 回复(0)

Java

不讲武德的芝士很年轻

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        return process(root);
    }
    public static int process(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int r = process(root.right);
        int l = process(root.left);
        return Math.max(r, l)+1;
    }
}

编辑于 2024-04-11 16:05:22 回复(0)

Java

你好，侦探先生

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if (root == null) {
            return 0;
        } else {
            int maxDepthLeft = maxDepth(root.left);
            int maxDepthRight = maxDepth (root.right);
            return 1 + Math.max(maxDepthLeft, maxDepthRight);
        }
    }
}

发表于 2024-03-28 09:58:39 回复(0)

Java

暴躁小姐姐

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

    }
}

发表于 2023-10-25 19:56:48 回复(0)

Java

李克雷

public class Solution {
    /**
     * 求给定二叉树的最大深度
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        if (null == root) {
            return 0;
        }
        int leftDeep = maxDepth(root.left);
        int rightDeep = maxDepth(root.right);
        return Math.max(leftDeep, rightDeep) + 1;
    }

}

发表于 2023-10-12 16:54:52 回复(0)

Java

做则必成的勇气和信心

public int maxDepth (TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Deque<TreeNode> qu=new LinkedList<>();
        if(root==null) return 0;
        qu.offer(root);
        int depth=0;
        while(!qu.isEmpty()){
            List<Integer> levelList=new ArrayList<>();
            int level=qu.size();
            for(int i=0;i<level;i++){
                TreeNode peek=qu.peekFirst();
                levelList.add(qu.poll().val);
                if(peek.left!=null) qu.offerLast(peek.left);
                if(peek.right!=null) qu.offerLast(peek.right);
            }
            //遍历完一层
            depth++;
        } 
        return depth;
    }

发表于 2023-07-13 20:17:09 回复(0)

Java

MorpheusNeo

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {

    private int maxDeep = 0;
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        dfs(root);
        return this.maxDeep;
    }

    public int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftMax = Math.max(0, dfs(node.left));
        int rightMax = Math.max(0, dfs(node.right));
        this.maxDeep = Math.max(this.maxDeep, Math.max(leftMax, rightMax) + 1);
        return Math.max(leftMax, rightMax) + 1;
    }
}

发表于 2023-05-08 10:12:22 回复(0)

Java

一颗宏心

public class Solution {

    public int maxDepth (TreeNode root) {
        if(root==null){
            return 0;
        }
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        int maxDepth = l>r?(l+1):(r+1);
        return maxDepth;
    }
}

发表于 2022-12-12 22:56:32 回复(0)

Java

dynamo1

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if (root == null) {
            return 0;
        }
        return doGetMaxDepth(root, 0);
    }

    private int doGetMaxDepth(TreeNode root,int depth) {

        if (root == null){
            return depth;
        }
        int l =  doGetMaxDepth(root.left, depth+1);
        int r =  doGetMaxDepth(root.right,  depth+1);
        
        return Integer.max(l, r);
    }
}

发表于 2022-11-05 13:38:05 回复(0)

Java

键盘都敲坏了.

dfs深度优先

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // root为空，返回深度0
        if(root == null){
            return 0;
        }
        
        // 向左子树遍历查找，拿到深度
        int l = maxDepth(root.left);
        // 向右子树遍历查找，拿到深度
        int r = maxDepth(root.right);
        
        // 返回 左子树 和 右子树 的深度取Max + 1
        // +1的原因是 加上当前层
        return Math.max(l,r) + 1;
    }
}

发表于 2022-11-03 13:19:06 回复(0)

Java

不会起名就这样吧

定义一个count和max，count每下一层加1，每上一层减1，如果max<count了，就让max=count；最后max就是二叉树的最大深度

    int count = 0;
    int max = count;
    public int maxDepth (TreeNode root) {
        // write code here
        dfs(root);
        return max;
    }
    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        count++;
        dfs(root.left);
        if(count>max){
            max = count;
        }
        dfs(root.right);
        if(count>max){
            max = count;
        }
        count--;
    }

发表于 2022-10-20 14:53:19 回复(0)

Java

牛客56756848号

递归，将问题分解为子问题，需要注意的是递归何时退出？当节点为null时，退出返回0

    public int maxDepth (TreeNode root) {
        // write code here

        if (root == null) {
            return 0;
        }

       return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

    }

发表于 2022-09-21 21:36:19 回复(0)

Java

aklddnddkwndje

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        return null==root?0:Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

发表于 2022-09-05 11:45:22 回复(0)