# Maximum Depth of Binary Tree

## Question

### Problem Statement

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.

#### Example

Given a binary tree as follow:

  1
/ \
2   3
/ \
4   5


The maximum depth is 3.

## 題解 - 遞迴

### C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxDepth(TreeNode *root) {
if (NULL == root) {
return 0;
}

int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);

return max(left_depth, right_depth) + 1;
}
};


### Java

/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}


## 題解 - 迭代(顯式使用 Stack)

### C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxDepth(TreeNode *root) {
if (NULL == root) {
return 0;
}

TreeNode *curr = NULL, *prev = NULL;
stack<TreeNode *> s;
s.push(root);

int max_depth = 0;

while(!s.empty()) {
curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left) {
s.push(curr->left);
} else if (curr->right){
s.push(curr->right);
}
} else if (curr->left == prev) {
if (curr->right) {
s.push(curr->right);
}
} else {
s.pop();
}

prev = curr;

if (s.size() > max_depth) {
max_depth = s.size();
}
}

return max_depth;
}
};


## 題解3 - 迭代(隊列)

### C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxDepth(TreeNode *root) {
if (NULL == root) {
return 0;
}

queue<TreeNode *> q;
q.push(root);

int max_depth = 0;
while(!q.empty()) {
int size = q.size();
for (int i = 0; i != size; ++i) {
TreeNode *node = q.front();
q.pop();

if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}

++max_depth;
}

return max_depth;
}
};


### Java

/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}

int depth = 0;
q.offer(root);
while (!q.isEmpty()) {
depth++;
int qLen = q.size();
for (int i = 0; i < qLen; i++) {
TreeNode node = q.poll();
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}

return depth;
}
}