JZ55 二叉树的深度

描述

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

 


 


 


 


 


 


 
，根节点的深度视为 1  
  
  
  
  
  
  
 。

方法1 递归

思路：

最大深度是所有叶子节点的深度的最大值 
 
 
 
 
 
 
，深度是指树的根节点到任一叶子节点路径上节点的数量 
   
   
   
   
   
   
  ，因此从根节点每次往下一层深度就会加1

 


 


 


 


 


 


 
。因此二叉树的深度就等于根节点这个1层加上左子树和右子树深度的最大值 
 
 
 
 
 
 
。而每个子树我们都可以看成一个根节点
 

 

 

 

 

 

 
，继续用上述方法求的深度
 

 

 

 

 

 

 
，于是我们可以对这个问题划为子问题              ，利用递归来解决： 终止条件： 当进入叶子节点后 

 
 

 
 

 
 

 
 

 
 

 
 

 
，再进入子节点













，即为空                     ，没有深度可言 
 
 
 
 
 
 
 
 
 
 
 
 
 
，返回0. 返回值： 每一级按照上述公式




















，返回两边子树深度的最大值加上本级的深度              ，即加1.

代码

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

方法2 层次遍历

思路

必须是一层一层的 
  
 
  
 
  
 
  
 
  
 
  
 
  
，那一层就是一个深度













，有的层可能会很多节点 
  
  
  
  
  
  
 ，有的层如根节点或者最远的叶子节点 
  
  
  
  
  
  
 ，只有一个节点

 


 


 


 


 


 


 
，但是不管多少个节点 
 
 
 
 
 
 
，它们都是一层 
   
   
   
   
   
   
  。因此我们可以使用层次遍历 
   
   
   
   
   
   
  ，二叉树的层次遍历就是从上到下按层遍历
 

 

 

 

 

 

 
，每层从左到右
 

 

 

 

 

 

 
，我们只要每层统计层数即是深度
 

 

 

 

 

 

 
。

代码

package esay.JZ55二叉树的深度; import java.util.LinkedList; import java.util.Queue; 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) { //方法1 /*if(root == null) { return 0; } else { return Math.max(TreeDepth(root.left), TreeDepth(root.right)) +1; }*/ if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int res = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } res++; } return res; } }