[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.

這道題是求一個二叉樹的深度。題目中對深度的定義是：從根節點到葉節點依次經過的結點（含根節點和葉節點）形成樹的一條路徑。最長路徑的長度為樹的深度。

我們可以按照上述定義來求得樹的所有路徑，從而得出最長路徑的長度。但是按照這種思路來寫程序有點麻煩。

我們可以從一個角度來理解樹的深度：如果一棵樹只有一個結點，它的深度為1。如果根結點只有左子樹而沒有右子樹，那麼樹的深度應該是其左子樹的深度加1；同樣如果根結點只有右子樹而沒有左子樹，那麼樹的深度應該是其右子樹的深度加1。如果既有右子樹又有左子樹呢？那該樹的深度就是其左、右子樹深度的較大值再加1。

按照上面的思路用遞歸的方法很容易實現，下面貼上代碼：

/**
 * Definition for binary tree
 * 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;
        }
        int left=maxDepth(root->left);
        int right=maxDepth(root->right);
        return (left>right?left:right)+1;
    }
};