LeetCode: Maximum Depth of Binary Tree

Iteration:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public: int maxDepth(TreeNode* root) { queue<pair<TreeNode*, int>> q; if(!root) return 0; q.push(make_pair(root,1)); while(!q.empty()){ pair<TreeNode*, int> cur=q.front(); q.pop(); if(cur.first->left !=NULL) q.push(make_pair(cur.first->left,cur.second+1)); if(cur.first->right !=NULL) q.push(make_pair(cur.first->right,cur.second+1)); if(cur.first->left==NULL && cur.first->right==NULL && q.empty()) return cur.second; } } };

Recursion:

1 2 3 4 5 6 7 8 9 10 11

class Solution { public: int maxDepth(TreeNode* root) { if(!root) return 0; int left=1; int right=1; if(root->left) left= maxDepth(root->left)+1; if(root->right) right= maxDepth(root->right)+1; return (left>right)?left:right; } };

Lintcode second:

BFS: queue store pair

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: /** * @param root: The root of binary tree. * @return: An integer */ int maxDepth(TreeNode *root) { // write your code here int res = 0; queue<pair<TreeNode*, int> > q; if(root) q.push(make_pair(root, 1)); while(!q.empty()){ TreeNode *curNode = q.front().first; int curLevel = q.front().second; res = max(res, curLevel); q.pop(); if(curNode->left) q.push(make_pair(curNode->left, curLevel + 1)); if(curNode->right) q.push(make_pair(curNode->right, curLevel + 1)); } return res; } };

BFS: two queues to track level
or use null or other special signal to track levels
or use a int count to track level