/**
 * 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 == nullptr) return 0;
　　　　 return max(maxDepth(root->left), maxDepth(root->right)) + 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 == nullptr) return 0;
        stack<pair<TreeNode*, int>> s;
        int deep = 0, cur_deep = 0;
        TreeNode* p = root;
        while(!s.empty() || p != nullptr) //若栈非空，则表示还有一些元素的右子树未访问，若p非空，则说明还有一些元素的左子树未访问，
        {
            while(p != nullptr)
            {
                s.push(pair<TreeNode*, int>(p, ++cur_deep)); //一直往左子树走，直到叶子节点
                p = p->left;
            }
            p = s.top().first;
            cur_deep = s.top().second;
            if(cur_deep > deep) deep = cur_deep;
            s.pop();
            p = p->right;
        }
        return deep;
    }
};