二、解题思路
- 递归查找
- 如果当前节点是空节点,那么返回0,同时也作为函数的递归出口
- 否则,返回
1 + max(left, right)
- 非递归查找
- 应用二叉树的后序遍历:当遍历到当前节点时,栈内的节点刚好就是当前节点的父节点.
三、解题代码
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
auto left = maxDepth(root->left);
auto right = maxDepth(root->right);
return 1 + max(left, right);
}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
int maxDep = 0;
TreeNode *p = root, *r = nullptr;
stack<TreeNode*> s;
while(p || !s.empty()){
if(p){
s.push(p);
p = p->left;
}
else{
p = s.top();
if(p->right && p->right != r)
p = p->right;
else{
maxDep = (maxDep > s.size() ? maxDep : s.size());
s.pop();
r = p;
p = nullptr;
}
}
}
return maxDep;
}
};
四、运行结果