首页 > 试题广场 >

二叉树的深度

[编程题]二叉树的深度
  • 热度指数：388382 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。

数据范围：节点的数量满足 ，节点上的值满足
进阶：空间复杂度 ，时间复杂度

假如输入的用例为{1,2,3,4,5,#,6,#,#,7}，那么如下图:

示例1

输入

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

输出

4
示例2

输入

{}

输出

0

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
披萨大叔头像 披萨大叔
非递归写法：层次遍历 
import java.util.Queue;
import java.util.LinkedList;

public class Solution {
	public int TreeDepth(TreeNode pRoot)
    {
    	if(pRoot == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(pRoot);
        int depth = 0, count = 0, nextCount = 1;
        while(queue.size()!=0){
            TreeNode top = queue.poll();
            count++;
            if(top.left != null){
                queue.add(top.left);
            }
            if(top.right != null){
                queue.add(top.right);
            }
            if(count == nextCount){
                nextCount = queue.size();
                count = 0;
                depth++;
            }
        }
        return depth;
    }
}
递归写法，比较简单，不解释： 
import java.lang.Math;
public class Solution {
	public int TreeDepth(TreeNode pRoot)
    {
    	if(pRoot == null){
            return 0;
        }
        int left = TreeDepth(pRoot.left);
        int right = TreeDepth(pRoot.right);
        return Math.max(left, right) + 1;
    }
}

发表于 2016-07-13 21:32:10 回复(50)
Python
GooHub头像 GooHub 
求树的深度，可以从层次遍历出发考虑
层次遍历可以使用队列完成，也可以使用递归完成，所以有两种方法
方法一：使用队列
class Solution:
    # 层次遍历
    def levelOrder(self, root):
        # write your code here
        # 存储最后层次遍历的结果
        res = []
        # 层数
        count = 0
        # 如果根节点为空，则返回空列表
        if root is None:
            return count
        # 模拟一个队列储存节点
        q = []
        # 首先将根节点入队
        q.append(root)
        # 列表为空时，循环终止
        while len(q) != 0:
            # 使用列表存储同层节点
            tmp = []
            # 记录同层节点的个数
            length = len(q)
            for i in range(length):
                # 将同层节点依次出队
                r = q.pop(0)
                if r.left is not None:
                    # 非空左孩子入队
                    q.append(r.left)
                if r.right is not None:
                    # 非空右孩子入队
                    q.append(r.right)
                tmp.append(r.val)
            if tmp:
                count += 1  # 统计层数
            res.append(tmp)
        return count

    def TreeDepth(self, pRoot):
        # write code here
        # 使用层次遍历
        # 当树为空直接返回0
        if pRoot is None:
            return 0
        count = self.levelOrder(pRoot)
        return count

方法二：使用递归方法
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        # 使用层次遍历
        # 当树为空直接返回0
        if pRoot is None:
            return 0
        # 方法2：使用递归
        # 如果该树只有一个结点，它的深度为1.如果根节点只有左子树没有右子树，
        # 那么树的深度为左子树的深度加1；同样，如果只有右子树没有左子树，
        # 那么树的深度为右子树的深度加1。如果既有左子树也有右子树，
        # 那该树的深度就是左子树和右子树的最大值加1.
        count = max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1
        return count

发表于 2018-05-06 10:52:43 回复(10)
牛客3154125号头像 牛客3154125号 
public class Solution {
	public int TreeDepth(TreeNode pRoot)
    {
    	return pRoot == null? 0 : Math.max(TreeDepth(pRoot.left),TreeDepth(pRoot.right)) + 1;
    }
}

发表于 2016-10-29 17:06:19 回复(7)
李长宇头像 李长宇
int TreeDepth(TreeNode* pRoot)
    {
     queue<TreeNode*> q;
        if(!pRoot) return 0;
        q.push(pRoot);
        int level=0;
        while(!q.empty()){
            int len=q.size();
            level++;
            while(len--){
                TreeNode* tem=q.front();
                q.pop();
                if(tem->left) q.push(tem->left);
                if(tem->right) q.push(tem->right);
            }
        }
        return level;
    }
发表于 2015-12-27 20:37:53 回复(20)
Python
华科平凡头像 华科平凡

python solution:


class Solution:
    def TreeDepth(self, pRoot):

        if pRoot==None:return 0
        return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1
发表于 2017-10-07 16:40:33 回复(6)
讲义气的芭乐想开了头像 讲义气的芭乐想开了
递归版本：
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        int leftnum=TreeDepth(root.left);
        int rightnum = TreeDepth(root.right);
        return Math.max(leftnum,rightnum)+1;
       
    }
}
非递归版本（层次遍历）
/*
经典的非递归层次遍历：利用辅助队列，先将头节点入队列，当队列不空时出队列的节点记为current，
当current左节点不空时入队列，其右节点不空时入队列，如此循环即可。
求深度：构造变量cur记录当前层访问到的节点数，width记录当前层的总个数，每当访问过一层层数deep++；
此种方法同时可以求最大宽度，访问第几层的第几个节点，是一种通用方法！
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null) return 0;
        TreeNode current;  //记录当前节点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();  //构造辅助队列
        int cur,width;           //cur记录访问到当前层的第几个,widtd为当前层的宽度
        int deep=0;            //初始深度为0；
        queue.offer(root);          //头结点入队列
        while(!queue.isEmpty()){        //队列不空 循环记录深度
            cur=0;                                //新的一层cur赋为0
            width=queue.size();           //当前队列里的节点即为该层的所有节点
            while(cur<width){               //循环访问该层的所有节点
                current=queue.poll();    //访问队列的头
                if(current.left!=null)       //左节点不空，左节点入队列
                    queue.offer(current.left);
                if(current.right!=null)     //右节点不空，右节点入队列
                    queue.offer(current.right);
                cur++;           //访问完当前节点后cur++
            }
            deep++;            //访问完一层，层数++;
        }
        return deep;
    }
}
发表于 2017-02-11 11:09:07 回复(2)
Giho头像 Giho 
Python 非递归解法



class Solution:   

    # 层次遍历    

    def levelOrder(self, root):        

        # 统计层数        

        count = 0        

        # 如果根节点为空，则返回空列表        

        if root is None:  return count        

        # 模拟一个队列储存节点        

        q = []        

        # 首先将根节点入队        

        q.append(root)        

        # 列表为空时，循环终止，说明没有新的叶子节点层        

        while len(q) != 0:            

            # 记录同层节点的个数            

            length = len(q)            

            for i in range(length):                

                # 将同层节点依次出队                

                r = q.pop(0)                

                if r.left is not None:                    

                    # 非空左孩子入队                    

                    q.append(r.left)                

                if r.right is not None:                    

                    # 非空右孩子入队                    

                    q.append(r.right)                

            count += 1              

        return count     

    def TreeDepth(self, pRoot):        

        # 使用层次遍历，当树为空直接返回0        

        if pRoot is None:  return 0        

        return self.levelOrder(pRoot)


编辑于 2018-09-27 01:17:00 回复(0)
crazychen头像 crazychen 
/*public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null && root.right==null) return 1;
        int left=0,right=0;
        if(root.left!=null) left = TreeDepth(root.left);
        if(root.right!=null) right = TreeDepth(root.right);
        return left>right?left+1:right+1;
    }
}

发表于 2015-04-12 19:30:42 回复(0)
Java
我去个地方啊头像 我去个地方啊

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

看到二叉树，递归基本没跑了，我们只要想好递归关系即可。我们假设已经正确拿到了root结点左右子树的最大深度，那么最后加一即可。

我的答案

public class Solution {
    public int TreeDepth(TreeNode root) {
        //递归的出口，root为0则返回0，这里可以理解为root为0那肯定没有层数了
        if(root == null){
            return 0;
        }
        //拿到左子树的最大深度
        int leftDep = TreeDepth(root.left);
        //拿到右子树的最大深度
        int rightDep = TreeDepth(root.right);
        //找出最大值，并且加上root这一层即可
        return Math.max(leftDep,rightDep) + 1;
    }
}
发表于 2019-03-11 10:48:12 回复(0)
崩溃DE够彻底︶｀头像 崩溃DE够彻底︶｀ 
public class Solution {
	private int deepmax=0;
    private int deep=0;
    public int TreeDepth(TreeNode pRoot)
    {
    if(pRoot==null)return 0;
    deep++;
    if(deep>deepmax)deepmax=deep;
    TreeDepth(pRoot.left); 
    TreeDepth(pRoot.right); 
    deep--;
    return deepmax;
    }
}

发表于 2016-07-13 22:32:53 回复(2)
Java
PinaColada头像 PinaColada
public class Solution {
    public int TreeDepth(TreeNode root) {

        if(root == null)  return 0;

        int leftDepth = TreeDepth(root.left);
        int rightDepth = TreeDepth(root.right);
        
        return (leftDepth > rightDepth) ? (leftDepth+1) : (rightDepth+1);
    }
}


//测试
public class DeepOfTreeTest {
    public static void main(String[] args) {
        // 构造一个树
        TreeNode root = new TreeNode(1);
        TreeNode left1 = new TreeNode(2);
        TreeNode right1 = new TreeNode(3);
        
        TreeNode left2 = new TreeNode(4);
        TreeNode left3 = new TreeNode(2);
        
        root.left = left1;
        root.right = right1;
        
        left1.left = left2;
        left2.left = left3;
        
        //
        DeepOfTree d = new DeepOfTree();
        System.out.println(d.TreeDepth(root));
    
    }

}


发表于 2019-03-05 11:02:39 回复(0)
吾生有你头像 吾生有你
用层序遍历求解，每遍历一层就加一 
import java.util.*;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null) return 0;
        ArrayList<TreeNode> arr=new ArrayList<>();
        arr.add(root);
        int count=0;
        while(arr.size()!=0){
            count++;
            for(int i=0; i<arr.size(); i++){
                TreeNode temp=arr.remove(0);
                if(temp.left!=null) 
                    arr.add(temp.left);
                if(temp.right!=null) 
                    arr.add(temp.right);
            }
        }
        return count;
    }
}

发表于 2018-07-31 10:21:02 回复(2)
打工不可能打工的头像 打工不可能打工的
递归解法 
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode cur = root;
        return bs(cur);
    }
    
    public int bs(TreeNode head) {
        if (head.left == null && head.right == null) {
            return 1;
        } else if (head.left != null && head.right == null) {
            return 1 + bs(head.left);
        } else if (head.left == null && head.right != null) {
            return 1 + bs(head.right);
        } else {
            return 1 + Math.max(bs(head.left), bs(head.right));
        }
    }
}

发表于 2018-07-10 16:05:51 回复(0)
Java
胖三斤66头像 胖三斤66 
//思路是层次遍历，通过插入特殊的结点new TreeNode(Integer.MIN_VALUE)来计算层次
public int TreeDepth(TreeNode root) {
        int depth=0;
        if(root!=null)
        {
        	Queue q=new LinkedList<TreeNode>();
        	q.offer(root);
        	q.offer(new TreeNode(Integer.MIN_VALUE));
        	while(!q.isEmpty())
        	{
        		TreeNode tmp=(TreeNode)q.poll();
        		if(tmp.val!=Integer.MIN_VALUE)
        		{
        			if(tmp.left!=null)
        				q.offer(tmp.left);
        			if(tmp.right!=null)
        				q.offer(tmp.right);
        		}
        		else//当遇到特殊节点时，说明当前层已经遍历完了同时下一层的所有节点已经全部入队了，在每层的最后压入一个特殊节点
        		{
        			depth++;
        			if(!q.isEmpty())//重点，不然会死循环
        				q.offer(new TreeNode(Integer.MIN_VALUE));
        		}
        	}
        }
        return depth;
    }

发表于 2017-03-19 15:14:38 回复(0)
kazeMace头像 kazeMace

python 递归版 一行代码

return 0 if (pRoot == None) else max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1
编辑于 2018-11-01 10:53:25 回复(1)
牛油1111头像 牛油1111 
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0; 
        return Math.max(TreeDepth(root.left) + 1, TreeDepth(root.right) + 1);
    }
}
发表于 2018-08-22 21:32:33 回复(1)
Thyme头像 Thyme 
public class Solution {
    public int TreeDepth(TreeNode root) {
        return TreeD(root,0);
    }
    private int TreeD(TreeNode root,int d){
        if (root==null)
            return d;
        else
            d++;
        return Math.max(TreeD(root.left,d),TreeD(root.right,d));
    }
}

发表于 2017-03-21 14:07:54 回复(0)
Java
Xy。头像 Xy。 
public class Solution {
	public int TreeDepth(TreeNode pRoot) {
        return pRoot == null ? 0 : Math.max(TreeDepth(pRoot.left), TreeDepth(pRoot.right)) + 1;
    }
}

发表于 2016-09-19 22:33:17 回复(1)
搬一块叫CV的砖头像 搬一块叫CV的砖 
//dfs，为了好读写长了一点
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==NULL)
            return 0;
        int MaxTreeDepth = 0;
    int leftDepth = TreeDepth(pRoot->left)+1;
        int rightDepth = TreeDepth(pRoot->right)+1;
        MaxTreeDepth = max(leftDepth,rightDepth);
        return MaxTreeDepth;
    }
};
发表于 2016-03-24 16:16:54 回复(0)
Shield_W头像 Shield_W 
public class Solution {
	public int TreeDepth(TreeNode pRoot) {
        if (pRoot == null) {
            return 0;
        }
        return Math.max(TreeDepth(pRoot.left), TreeDepth(pRoot.right)) + 1;
    }
}

发表于 2016-07-19 17:29:47 回复(0)
提交观点

问题信息

树
来自：“一战通offer”互...
难度：
1175条回答 111740浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树的深度

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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