首页 > 试题广场 >

二叉树的最大深度

[编程题]二叉树的最大深度
  • 热度指数：136855 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
（注：叶子节点是指没有子节点的节点。）


数据范围：，树上每个节点的val满足
要求： 空间复杂度 ,时间复杂度
示例1

输入

{1,2}

输出

2
示例2

输入

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

输出

3

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python 3
来个offer叭！头像 来个offer叭！ 
# 非递归，使用队列
import queue
class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        depth = 0
        if not root: return depth
        q = queue.Queue()
        q.put(root)
        while not q.empty():
            # 当前层的结点个数
            n = q.qsize()
            for i in range(n):
                node = q.get()
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            # 遍历完当前层后，深度+1
            depth += 1
        return depth

发表于 2022-07-21 16:47:45 回复(0)
Python
wengJJ头像 wengJJ
Python
递归，使用普通迭代则每次都需要判断左右节点 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def maxDepth(self , root ):
        # write code here
#         递归 终止条件为到达叶子节点 
        if not root:
            return 0
        left_len = self.maxDepth(root.left)
        right_len = self.maxDepth(root.right)
        return 1+max(left_len,right_len)
            


发表于 2021-04-20 13:08:18 回复(0)
阿姨我不想努力了zz头像 阿姨我不想努力了zz
两种方法，一种用队列层次遍历。一种用递归。本次是递归. 
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if(root==null) return 0;
        int left=0,right=0;
        if(root.left!=null){
            left+=maxDepth (root.left);
        }
        if(root.left!=null){
            right+=maxDepth (root.right);
        }
        
        return Math.max(left,right);
        
        
    }
}

发表于 2021-03-09 12:29:54 回复(0)
Java
tornado123头像 tornado123 
    public int maxDepth (TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

发表于 2020-10-14 09:58:02 回复(0)
Java
Zfirsty头像 Zfirsty 
public class Solution {
    public int maxDepth(TreeNode root){
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

发表于 2017-07-27 11:07:27 回复(0)
T+T头像 T+T 


public static int maxDepth(TreeNode root) { if (root==null)return 0; return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
编辑于 2017-03-21 17:32:07 回复(0)
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 left > right ? left+1 : right +1;
    }

发表于 2021-12-03 20:00:59 回复(0)
C/C++
努力的牛牛头像 努力的牛牛 
    /*
    * 目的：求最大深度
    * 方法：递归
    */
    int maxDepth(TreeNode *root) {
        if (root==nullptr)
            return 0;
        return 1+max(maxDepth(root->left), maxDepth(root->right));
    }
发表于 2019-12-07 14:54:04 回复(0)
C/C++
华科平凡头像 华科平凡 
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if (root==NULL){return 0;}
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

C++ solution

发表于 2017-10-27 09:13:41 回复(0)
Java
阿拉要洗澡头像 阿拉要洗澡
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            
            return 0;
            
        }
        
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        
        if(left>right){
            
            return left+1;
        }else{
            
            return right+1;
            
        }
        
        
    }
}
发表于 2017-08-24 17:01:12 回复(0)
novo头像 novo 
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(root == NULL) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

发表于 2016-04-12 22:21:20 回复(3)
JacobGo！头像 JacobGo！ 
/*
	 * 解法一：
	 * 递归解法，非常简洁
	 */
	public int maxDepth(TreeNode root) {
		if(root==null)
			return 0;
		return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
	}
	
	
	
	/*
	 * 解法二： 使用queue进行层序遍历
	 */
	public int maxDepth_1(TreeNode root) {
		if (root == null)
			return 0;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		int res = 0;
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				if (node.left != null)
					queue.add(node.left);
				if (node.right != null)
					queue.add(node.right);
			}
			res++;
		}

		return res;
	}

发表于 2017-08-06 10:54:04 回复(1)
StrongYoung头像 StrongYoung 
	  public int maxDepth(TreeNode root){
		  if(root==null)
			  return 0;
		  int lDepth = maxDepth(root.left);
		  int rDepth = maxDepth(root.right);
		  return 1+(lDepth>rDepth?lDepth:rDepth);
	  }

发表于 2015-10-02 10:30:25 回复(0)
Java
Vtech头像 Vtech 
public class Solution {
    public int maxDepth (TreeNode root) {
        return root==null?0:1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

发表于 2021-10-21 09:02:43 回复(0)
watson_头像 watson_
递归，两行代码： 
public int maxDepth (TreeNode root) {
    if(root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}


发表于 2020-10-28 15:39:26 回复(0)
胖十斤换网名的阿琛头像 胖十斤换网名的阿琛 
class Solution {
public:
    int maxDepth(TreeNode *root) {
        return root ? (max(maxDepth(root->left),maxDepth(root->right)) + 1) : 0;
        
    }
};

发表于 2019-10-08 15:14:28 回复(0)
武培轩头像 武培轩

Leetcode#104. Maximum Depth of Binary Tree（二叉树的最大深度）

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    /**
     * 递归
     *
     * @param root
     * [@return](/profile/547241) */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
    }
    /**
     * 非递归，层次遍历
     *
     * @param root
     * [@return](/profile/547241) */
    public int maxDepth_2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        int start = 0;
        int end = 1;
        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            start++;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
            if (start == end) {
                start = 0;
                end = queue.size();
                depth++;
            }
        }
        return depth;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}
编辑于 2018-09-12 15:55:24 回复(0)
阿诺41头像 阿诺41 
if (root == NULL) { return 0; }
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
发表于 2017-08-29 21:24:05 回复(0)
C++
ZZZ2021头像 ZZZ2021
一行即可 
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root?1 + max(maxDepth(root->left), maxDepth(root->right)):0;
    }
};


发表于 2023-07-24 10:55:58 回复(0)
cqu后起之秀头像 cqu后起之秀 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int depth = 0;
    int res = 0;
    int road = 0;
     
    void trasvel(TreeNode* root){
        if(root == NULL) {
            res = max(res, road);
            return;
        }
        road++;
        trasvel(root->left);
        trasvel(root->right);
        road--;
    }
    int maxDepth(TreeNode* root) {
        // write code here
        trasvel(root);
        return res;
    }
};

发表于 2022-03-16 02:29:42 回复(0)
提交观点

问题信息

树 dfs
来自：经典编程练习-简单卷
难度：
336条回答 25855浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号