leetcode——[104]Maximum Depth of Binary Tree二叉树的最大深度

题目

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

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],

  3
 / \
9  20
  /  \
 15   7

return its depth = 3.

解题方法

递归

使用递归对树进行遍历，先求左右子树的深度，进行比较后，去较大值加1即为以该节点为根的树的最大深度，递归求得树的最大深度。这段代码时间复杂度为O(2^n)，n为树的深度，跑了0ms，超过100%的java提交。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return numOfChildren(root);
    }

    private static int numOfChildren(TreeNode parent) {
        if (parent == null) {
            return 0;
        }
        int lDepth = numOfChildren(parent.left);
        int rDepth = numOfChildren(parent.right);
        int depth = lDepth > rDepth ? lDepth + 1 : rDepth + 1;
        return depth;
    }
}