首页 > 试题广场 >

二叉树的最大深度

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

热度指数：138334 时间限制：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 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)

Java

我是菜只因

public int maxDepth (TreeNode root) {
// write code here
if(root == null){
return 0;
}
//返回的最大深度
int max = 0;
//左子树的最大深度
int maxL = 0;
//右子树的最大深度
int maxR = 0;
if(root.left != null){
//如果左子树不为空，则对递归调用
maxL = maxDepth(root.left);
}
if(root.right != null){
//如果右子树不为空，则递归的调用
maxR = maxDepth(root.right);
}
//最后比较左右子树的最大深度，选择大的一个+1即可
return maxL > maxR ? maxL+1:maxR+1;
}
}

发表于 2022-08-14 16:43:05 回复(0)

Java

牛客用户007

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;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return left > right ? left + 1 : right + 1;
    }
}

发表于 2022-08-03 12:25:49 回复(0)

Java

624huiguorou

二叉树的深度

可设置全局变量r，然后preorder在形参里对当前深度+1。

也可以在原返回int函数实现，return 1+Math.max(maxDepth(root.left), maxDepth(root.right));【左子树和右子树最大的深度+1】

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    
    int r = 1;
    
    public int maxDepth (TreeNode root) {
        // write code here
        if(root == null) return 0;
        preorder(root, 1);
        return r;
    }
    
    public void preorder(TreeNode root, int d){
        if(root != null){
            if(d > r) r = d;
            preorder(root.left, d+1);
            preorder(root.right, d+1);
        }
    }
    
//     public int maxDepth (TreeNode root) {
//         // write code here
//         if(root == null) return 0;
//         return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
//     }
}

发表于 2022-07-24 15:57:37 回复(0)

Java

yxjing

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
        ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
        int level=levelorder(root,list);
        return level;
    }
    public int levelorder(TreeNode root,ArrayList<ArrayList<Integer>> list){
        int level=0;
        if(root==null){return 0;}
        Deque<TreeNode> deque=new LinkedList<TreeNode>();
        ArrayList<Integer> sublist=new ArrayList<Integer>();
        deque.addLast(root);
        while(!deque.isEmpty()){
            int num=deque.size();
            for(int i=0;i<=num-1;i++){
                TreeNode cur=deque.removeFirst();
                if(cur.left!=null){deque.addLast(cur.left);}
                if(cur.right!=null){deque.addLast(cur.right);}
                sublist.add(cur.val);
            }
            list.add(sublist);
            level=level+1;//每次加入一层的节点sublist---level=level+1
        }
        return level;
    }
}

发表于 2022-07-16 15:21:25 回复(1)