剑指offer—二叉树的深度 解答

剑指offer—二叉树的深度

题目描述

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 

思路

递归DFS—深度优先搜索遍历

流程:

  1. 遍历根节点,深度为0
  2. 遍历其左右子树,递归传入的深度+1,递归遍历,返回左右子树中深度的最大值
  3. 直到节点为空 返回深度

代码

public class Solution {
    public int TreeDepth(TreeNode root) {
         return dfs(0,root);
    }
    public int dfs(int deepth,TreeNode node){
        if(node==null) return deepth;
        return Math.max(dfs(deepth+1,node.left), dfs(deepth+1,node.right));
    }
}
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        else return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/btree-depth.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!