面试题55 - I. 二叉树的深度

Description

难度：简单15
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示：

  1. 节点总数 <= 10000

    Solution

    解答一：

    前序遍历二叉树，计算递归的深度，找到最长的递归深度即可
    1. class Solution {
    2.  int maxDepth;
    3.  public int maxDepth(TreeNode root) {
    4.      maxDepth = 0;
    5.      int depth = 0;
    6.      pre(root, depth+1);
    7.      return maxDepth;
    8.  }
    9.  public void pre(TreeNode node, int depth){
    10.      if(node == null ){
    11.          if((depth - 1) > maxDepth)
    12.              maxDepth = depth - 1;
    13.          return; 
    14.      }
    15.      pre(node.left, depth+1);
    16.      pre(node.right, depth + 1);
    17.  }
    18. }
    执行结果：
    执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户。
    内存消耗 :39.8 MB, 在所有 Java 提交中击败了100.00%的用户。

解答二：

后序遍历，返回左右子树中深度最大的数再加上 1

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         return postRecursion(root);
  4.     }
  5.     public int postRecursion(TreeNode node){
  6.         if (node == null)
  7.             return 0;
  8.         int leftNums = postRecursion(node.left);
  9.         int rightNums = postRecursion(node.right);
  10.         return Math.max(leftNums, rightNums) + 1;
  11.     }
  12. }

执行结果：通过
显示详情
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.5 MB, 在所有 Java 提交中击败了70.07%的用户