一、题目描述

二、解题思路

• 递归查找
  • 如果当前节点是空节点，那么返回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;         
    }
};

四、运行结果