LintCode 97. Maximum Depth of Binary Tree 原创Java参考解答

LintCode 97. Maximum Depth of Binary Tree 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/maximum-depth-of-binary-tree/

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.

Example

Given a binary tree as follow:

  1
 / \ 
2   3
   / \
  4   5

The maximum depth is 3.

解题思路

题目是求二叉树的最大深度。

用分治思想解决这道题。分开算出左右子树的深度,再合并计算整棵树的最大深度。

参考代码

/** 
 * Definition of TreeNode: 
 * public class TreeNode { 
 *     public int val; 
 *     public TreeNode left, right; 
 *     public TreeNode(int val) { 
 *         this.val = val; 
 *         this.left = this.right = null; 
 *     } 
 * } 
 */ 
public class Solution { 
    /** 
     * @param root: The root of binary tree. 
     * @return: An integer. 
     */ 
    public int maxDepth(TreeNode root) { 
        if (root == null) { 
            return 0; 
        } 
         
        int leftDepth = maxDepth(root.left); 
        int rightDepth = maxDepth(root.right); 
         
        return Math.max(leftDepth, rightDepth) + 1; 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总

发表评论

电子邮件地址不会被公开。 必填项已用*标注