LeetCode：求二叉树的深度

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.

二叉树的深度定义为根节点到距离根节点最远的叶子节点之间节点的数量。

解题思路：

若二叉树为空，则深度应该为0；

若二叉树根节点没有孩子，则深度为1；

若根节点只有左孩子或者只有右孩子，则二叉树的深度应该为以左孩子为根节点的子树或者以右孩子为根节点的子树的深度加1（二叉树根节点）；

若根节点既有左孩子又有右孩子，则二叉树的深度应该为以左孩子或者右孩子为根节点的两棵子树的深度之间的大者加1。

根据以上思路，可知，要求二叉树的深度，必须知道其左子树和右子树的深度，故可以使用递归的思想来解决。

代码如下：

/** * 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;        }        else{            int leftDepth = maxDepth(root->left);            int rightDepth = maxDepth(root->right);            return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;        }    }};