LeetCode_104_Maximum Depth of Binary Tree

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.

题目分析：

    给定一个二叉树，求出他的最大深度。

    采用递归的方法，不断求解l,r的深度，当l or r = NULL时 返回 0, 每次调用递归函数时深度+1。并不断取l,r的最大值。

Solution

/**
 * 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)
            return 0;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        
        return max(l,r)+1;
    }
};

对于递归掌握不是特别熟练，验证思路

下面以(‘x’)表示值为x的结点（仅针对上图以方便表达）

　　maxDepth(‘5’) = max( maxDepth(‘4’), maxDepth(‘7’) )+1

　　maxDepth(‘4’) = max( maxDepth(‘3’), 0 )+1

　　maxDepth(‘7’) = max( maxDepth(‘2’), 0 )+1

　　maxDepth(‘3’) = max( maxDepth(‘-1’), 0 )+1

　　maxDepth(‘2’) = max( 0 ,0 )+1

　　maxDepth(‘-1’) = max( 0, 0 )+1

所以

　　maxDepth(‘-1’) = 1;

　　maxDepth(‘2’) = 1;

　　maxDepth(‘3’) = 2;

　　maxDepth(‘7’) = 2;

　　maxDepth(‘4’) = 3;

　　maxDepth(‘5’) = 4;

分解为各个子树，深度求解亦正确。