本题有多种解法:
- 后序遍历,每次返回以当前节点为根节点的子树的深度
- 先序遍历,记录根节点到当前节点的高度,如果是叶子,则更新max值
下面采用第一种思路:
class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int maxDepth(TreeNode* root) { // write code here return postOrder(root); } int postOrder(TreeNode* root) { if (!root) return 0; int left = 1 + postOrder(root->left); int right = 1 + postOrder(root->right); return left > right ? left : right; } };