首页 > 试题广场 >

二叉树的深度

[编程题]二叉树的深度
  • 热度指数:383395 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度,根节点的深度视为 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)
求树的深度,可以从层次遍历出发考虑
层次遍历可以使用队列完成,也可以使用递归完成,所以有两种方法
方法一:使用队列
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)
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 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)
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)
/*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)

题目描述

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

解题思路

看到二叉树,递归基本没跑了,我们只要想好递归关系即可。我们假设已经正确拿到了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)
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)
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)
//思路是层次遍历,通过插入特殊的结点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)

python 递归版 一行代码

return 0 if (pRoot == None) else max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1
编辑于 2018-11-01 10:53:25 回复(1)
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)
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)
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)
//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)
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)