Maximum Depth of Binary Tree

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.

===========================================================================

 

Aparently, recursive solution came into my mind as soon as I've finished reading the problem. Here's the code:

1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 int maxDepth(TreeNode *root) {13     // Start typing your C/C++ solution below14     // DO NOT write int main() function15 16     //Recursive Solution:17     //There's 2 conditions: 18     //1 root is NULL, break point, should return 0 as its depth19     //2 root is not NULL, should return its max child depth plus 120     if(NULL == root){21         return 0;22     }23     return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;24 }25 };

----------------------------------------------------------------------

But I wondered if there's a non-recursive solution. So I use a stack to store the traverse path. Additionally, I used a pair to store node status, which indicated if current node's children have been visited or not. here's the code:

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int maxDepth(TreeNode *root) {13         // Start typing your C/C++ solution below14         // DO NOT write int main() function15         if(NULL == root){16             return 0;17         }18         int max_depth = 0;19 20         //node status 0:  neither left nor right has been visited21         //node status 1:  only left has been visited22         //node status 2:  left and right all have been visited23         stack
     
      
        > s;24         //push root into stack, initail status is 0, because both children haven't been visited.25         s.push(make_pair(root,0));26         pair
       
        * p_pair;27         while(!s.empty()){28             //fetch the top node in stack29             p_pair = &(s.top());30             31             //neither left nor right has been visited32             //visit left child, then set the status code to 133             if(p_pair->second == 0) {34                 if(NULL != p_pair->first->left){35                     s.push(make_pair(p_pair->first->left,0));36                 }37                 p_pair->second = 1;38             }39             40             //only left has been visited,41             //visit right child, then set the status code to 242             else if(p_pair->second == 1) {43                 if(NULL != p_pair->first->right){44                     s.push(make_pair(p_pair->first->right,0));45                 }46                 p_pair->second = 2;47             }48             49             //left and right all have been visited50             //pop this node out of stack. and do nothing.51             else if(p_pair->second == 2) {52                 s.pop();53             }54             55             //current node's depth is equal to the size of stack56             max_depth = max((int)(s.size()), max_depth);57         }58         59         return max_depth;60     }61 };