【LeetCode】104、二叉树的最大深度

104、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.

  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。

C++，用时16ms，内存19M

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root==NULL)
            return 0;
        if (root->left==NULL && root->right==NULL)
            return 1;
        
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        if (leftDepth > rightDepth) {
            return leftDepth+1;
        }
        else {
            return rightDepth+1;
        }
    }
};

进行Recursion探索时完成的，其他解法后续补充。