leetcode筆記：Maximum Depth of Binary Tree

leetcode筆記：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.

二. 題目分析

這道題和Minimum Depth of Binary Tree一題相似，這個是求最大深度的，就是對二叉樹進行遞歸，然後將子樹的最大深度進行返回，最終得到這個樹的最大深度。

這個方法的時間復雜度為：O(n)，空間復雜度為：O(logn)。

三. 示例代碼

// 時間復雜度為O(n)，空間復雜度O(logn)
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 Result = 1;  
        int Left = maxDepth(root->left);  
        int Right = maxDepth(root->right);  

        if (Left * Right)  
        {  
            Result += Left < Right? Right : Left;  
        }  
        else  
        {  
            Result += Right + Left;  
        }  

        return Result;  
    }  
};

四. 小結

無。