算法20(递归)-二叉树的深度

算法递归二叉树 dfs

发布时间 : 2020-07-04 16:36

字数:259 阅读 :

评论:

题目：

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

/
9 20
/
15 7
return its depth = 3.

给一个二叉树，将他的最大深求出来并且进行输出
1.采用递归的思想，停止递归的条件是根节点没有左子树并且没有右子树，就返回0，
2.递归做什么事情，递归左子树，递归右子树，找到两个子树深度最大值，再进行加3.返回的就是两个子树深度最大值加1

package com.cxy.recursive;

import com.cxy.linkedtable.TreeNode;

import java.util.List;

/**
 * 二叉树的深度优先搜索递归实现
 */
public class BinaryTreeDepth {

  public int maxDepth(TreeNode root) {
    if(root == null){return 0;}
    int leftDeep = maxDepth(root.left);
    int rightDeep = maxDepth(root.right);
    return Math.max(leftDeep, rightDeep)+1;
  }


  public static void main(String[] args){
    TreeNode left = new TreeNode(1, null, null);
    TreeNode right = new TreeNode(2, null, null);
    TreeNode root = new TreeNode(0, left, right);
    int depth = new BinaryTreeDepth().maxDepth(root);
    System.out.println(depth);
  }

}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1371769065@qq.com