剑指 Offer 55 - I. 二叉树的深度

解题思路：递归

递归的解题步骤：

  1. 将原问题分解成子问题，并确定子问题和原问题之间的递推关系
  2. 确定 base case 的返回值

已知一棵树的根节点为：TreeNode root

该树的深度表示为：maxDepth(root)

该树的左子树深度表示为：maxDepth(root.left) ；该树的右子树深度表示为：maxDepth(root.right)

子问题和原问题之间的递推关系为：

  1. maxDepth(root) = Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;

当 root 为空时，说明我们遍历这棵树已经越过了叶节点，此时返回深度为 0

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int maxDepth(TreeNode root) {
  12.         if(root == null){
  13.             return 0;
  14.         }
  15.         return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
  16.     }
  17. }

复杂度分析

  • 时间复杂度：O(N)

我们通过递归遍历树的深度，需要遍历到每一个节点，所以时间复杂度为：O(N)

  • 空间复杂度：O(N)

当一棵二叉树退化至链表时，调用递归栈的深度为 O(N)