首页 > 试题广场 >

二叉树的深度

[编程题]二叉树的深度

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

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

数据范围：节点的数量满足 $0 \le n \le 100$ ，节点上的值满足 $0 \le val \le 100$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

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

示例1

输入

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

输出

示例2

输入

{}

输出

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

算法知识视频讲解

Java

进入人才池

public class Solution {
    public int TreeDepth(TreeNode root) {
        if ( root == null ) return 0;
        return 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
    }
}

发表于 2023-04-01 21:34:28 回复(0)

Java

Hadoopdoop

// 递归层次遍历
import java.util.*;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue1 = new LinkedList();
        Queue<TreeNode> queue2 = new LinkedList();
        queue1.add(root);
        // 广度遍历
        int depth = deepth(queue1, queue2, 0);
        return depth;
    }
 
    private int deepth(Queue<TreeNode> queue1, Queue<TreeNode> queue2, int depth) {
        if (!queue1.isEmpty() && queue2.isEmpty()) {
            while (!queue1.isEmpty()) {
                TreeNode node = queue1.poll();
                if (node.left != null) {
                    queue2.add(node.left);
                }
                if (node.right != null) {
                    queue2.add(node.right);
                }
            }
            return deepth(queue1, queue2,  depth += 1);
        } else if (queue1.isEmpty() && !queue2.isEmpty()) {
            while (!queue2.isEmpty()) {
                TreeNode node = queue2.poll();
                if (node.left != null) {
                    queue1.add(node.left);
                }
                if (node.right != null) {
                    queue1.add(node.right);
                }
            }
            return deepth(queue1, queue2,  depth += 1);
        } else  {
            return depth;
        }
    }
}

发表于 2023-03-08 13:23:38 回复(0)

Java

帅的烦燥

/**

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) {

return geteLeavl(root,1);

}

public int geteLeavl(TreeNode root, int leavl) {

if(root==null){

return leavl;

}

int ldata = 0;

int rdata = 0;

if (root.left != null) {

ldata = geteLeavl(root.left,leavl+1);

}

if (root.right != null) {

rdata = geteLeavl(root.right,leavl+1);

}

return ldata == 0 && rdata == 0 ?leavl : ldata > rdata ? ldata : rdata;

}

发表于 2022-11-30 18:22:23 回复(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 {
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}


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


}

发表于 2022-06-21 23:08:40 回复(0)

Java

NorthXwind

二叉树递归简易写法

public class Solution {
    private int res = 0;
    public int TreeDepth(TreeNode root) {
        dfs(root, 1);
        return res;
    }

    public void dfs(TreeNode root, int deep) {
        if (root == null) {
            return;
        }
        res = Math.max(res, deep);
        dfs(root.left, deep + 1);
        dfs(root.right, deep + 1);

    }
}

发表于 2022-06-17 15:13:42 回复(0)

Java

txy_钟琛

public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        return 1 + Math.max(TreeDepth(root.left),TreeDepth(root.right));
    }
}

发表于 2022-05-28 11:52:52 回复(0)

Java

小泽HK

public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null) return 0;
// 获取左孩子的高度
int lf = TreeDepth(root.left);
// 获取右孩子的高度
int rt = TreeDepth(root.right);
// 最大孩子的高度+1即为本节点在树上的高度
return lf > rt?lf +1:rt+1;
}
}

发表于 2022-05-05 19:14:55 回复(0)

Java

小刚Ethan

public class JZ55 {
    /**
     * Description: 经典递归<br>
     */
    public int TreeDepth(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
    }
}

发表于 2022-04-06 11:50:04 回复(0)

Java

zhenggw

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

发表于 2022-03-25 11:20:24 回复(0)

Java

IF_2000

递归写法，简洁。

public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        else return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
    }
}

发表于 2022-03-17 16:33:54 回复(0)

Java

624huiguorou

在一个函数里递归，方法返回的是该结点左子树或右子树的深度。是从下到上来算深度的，按照这个语义的话，root结点的深度为1，然后加上root左子树和右子树的最大深度。

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null) return 0;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        //left和right的意义是该结点左子树和右子树深度，结果取最大
        return 1 + Math.max(left, right);
    }
}

拆开方法，用另一个方法的参数进行深度计算，是从上到下计算深度。

public class Solution {
    
    public int maxDepth = 0;
    
    public int TreeDepth(TreeNode root) {
        handle(root, 1);
        return maxDepth;
    }
    
    public void handle(TreeNode root, int count) {
        if(root == null) return ;
        if(count > maxDepth) maxDepth = count; 
        handle(root.left, count + 1);
        handle(root.right, count + 1);
    }
}

发表于 2022-03-07 18:34:45 回复(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 {
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
         Queue<TreeNode> queue = new LinkedList<>();
         queue.offer(root);
             int depth = 0;
         while(!queue.isEmpty()){
             int size = queue.size();
                 depth++;
             while(size != 0){
                 TreeNode cur = queue.poll();
                 if(cur.left != null){
                     queue.offer(cur.left);
                 }
                 if(cur.right != null){
                     queue.offer(cur.right);
                 }
                 size--;
             }
         }
         return depth;
   
            //方法2
//     public int max = 0;
//     public void TreeNodeHelper(TreeNode root,int cur){
//         if(root == null){
//             //去重
//             if(max < cur){
//                 max = cur;
//             }
//             return;
//         }
//         TreeNodeHelper(root.left,cur + 1);
//         TreeNodeHelper(root.right,cur + 1);
//     }
//     public int TreeDepth(TreeNode root) {
//         if(root == null){
//             return 0;
//         }
//         int depth = 0;
//         TreeNodeHelper(root,depth);
//         return max;
        
        
        
    //方法1
//         int leftTree = TreeDepth(root.left);
//         int rightTree = TreeDepth(root.right);
//         return (leftTree > rightTree) ? leftTree + 1 : rightTree + 1;
        
    }
}

发表于 2022-02-13 20:14:37 回复(0)

Java

牛客989812257号

递归：

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return Math.max(left,right)+1;
    }
}

非递归：

import java.util.Deque;
import java.util.LinkedList;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        Deque<TreeNode> queue = new LinkedList();
        queue.add(root);
        int depth = 0;
        while(!queue.isEmpty()){
            depth++;
            int queueSize = queue.size();
            for(int i=0;i<queueSize;i++){
                TreeNode node = queue.pollFirst();
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
        }
        return depth;
    }
}

发表于 2022-01-27 00:00:58 回复(0)

Java