Maximum Depth of Binary Tree [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.

Solutions: here I will give three solutions to this problem including both iteration and recursion.

• DFS (recursion) ;
• BFS (iteration);
• DFS (iteration; postorder traversal) [check here for iterative postorder traversal].

   /*******************************SOLUTION 1***********************************/

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};

   /*******************************SOLUTION 2***********************************/

class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(!root) return 0;
        queue<TreeNode *> q;
        q.push(root);
        int curNum=1, nxtNum=0;
        int maxHeight=0;
        while(!q.empty()){
            TreeNode* cur = q.front();
            q.pop();
            curNum--;
            //Push two children
            if(cur->left!=NULL){
                q.push(cur->left);
                nxtNum++;
            }
            if(cur->right!=NULL){
                q.push(cur->right);
                nxtNum++;
            }
            if(curNum==0){
                maxHeight++;
                if(nxtNum==0)
                    break;
                swap(curNum, nxtNum);
            }
        }
        return maxHeight;
    }
};

   /*******************************SOLUTION 3***********************************/

class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(!root) return 0;
        stack<TreeNode *> s;
        s.push(root);
        int maxHeight = 0;
        int curHeight = 0;
        TreeNode* pre=NULL;
        while(!s.empty()){
            TreeNode* cur = s.top();
            //Go down
            if(pre==NULL || pre->left==cur || pre->right==cur){
                curHeight++;
                if(cur->left!=NULL)
                    s.push(cur->left);
                else if (cur->right!=NULL)
                    s.push(cur->right);
                else {
                    s.pop();
                    maxHeight = max(maxHeight, curHeight);
                }
            }
            //Go up
            else{
                curHeight--;
                //From left child
                if(cur->left==pre){
                    if(cur->right!=NULL)
                        s.push(cur->right);
                    else
                        s.pop();
                }
                //From right child
                else
                        s.pop();
            }
            pre = cur;
        }
        return maxHeight;
    }
};