[剑指offer] 二叉树的深度

题目描述

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

解题思路

法一:递归法。求二叉树的深度,就是求左子树、右子树的中深度最大的加上一个根节点,依此递归即可。 法二:层次遍历。每遍历一层,deep 加 1,直接到最后一层,输出 deep。

参考代码

法一:递归法

/**
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;
        int left = TreeDepth(root.left) + 1;
        int right = TreeDepth(root.right) + 1;
        return left > right ? left : right;
    }
}

法二:层次遍历

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        int deep = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int start = 0, end = 1;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            start ++;
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
            if(start == end){
                end = queue.size();
                start = 0;
                deep ++;
            }
        }
        return deep;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

请你对Java中树的了解有多少?

树 1200101班的学生信息表如图6.1所示,其中学生被分到了不同的学习小组,第一组组长是李华,组员有王丽、张阳、赵斌; 第二组组长是孙琪,组员有马丹; 第三...

3885
来自专栏武培轩的专栏

剑指Offer-按之字形顺序打印二叉树

package Tree; import java.util.ArrayList; import java.util.LinkedList; import j...

2844
来自专栏Python专栏

【数据结构与算法】一起搞定面试中的二叉树题目(二)

2263
来自专栏熊二哥

深入入门系列--Data Structure--04树

终于有机会重新回头学习一下一直困扰自身多年的数据结构了,赶脚棒棒哒。一直以来,对数据结构的掌握基本局限于线性表,稍微对树有一丢丢了解,而对于图那基本上就是不懂(...

1919
来自专栏尾尾部落

[剑指offer] 对称的二叉树

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

2173
来自专栏书山有路勤为径

二叉树基础知识

树是n(n>=0)个节点的有限集,且这些节点满足如下关系: (1)有且仅有一个节点没有父结点,该节点称为树的根。 (2)除根外,其余的每个节点都有且仅有一个...

732
来自专栏desperate633

LintCode 二叉树的层次遍历 II题目代码

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)

984
来自专栏张俊红

数据结构—树与二叉树

之前谈到的线性表、栈和队列都是一对一的数据结构,但是现实中也存在很多一对多的数据结构,这篇要写的就是一种一对多的数据结构———树。全文分为如下几部分:

1413
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

4546
来自专栏程序生活

二叉树的深度

题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 代码实现 递归实现 # ...

2674

扫码关注云+社区

领取腾讯云代金券