【leetcode】Maximum Depth of Binary Tree

Question ：

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.

Anwser 1 ： DFS

/**
 * 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 == NULL) return 0;
        
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        
        return l > r ? l + 1 : r + 1;
    }
};

More simpe ：

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

Anwser 2 ： BFS in queue

class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root == NULL) return 0;
        
        queue<TreeNode *> Q;
        
        Q.push(root);
        int count = 1;
        int depth = 0;
        while(!Q.empty()){
            TreeNode *tmp = Q.front();
            Q.pop();
            count--;
            
            if(tmp->left){
                Q.push(tmp->left);
            }
            if(tmp->right){
                Q.push(tmp->right);
            }
            
            if(count == 0){
                depth++;            // one row is end, add a depth
                count = Q.size();   // next row count
            }
        }
        return depth;
    }
};

Anwser 3 ： BFS in stack

class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root == NULL) return 0;
        
        stack<TreeNode*> S;
        
        int maxDepth = 0;
        TreeNode *prev = NULL;
        
        S.push(root);
        while (!S.empty()) {
            TreeNode *curr = S.top();
            
            if (prev == NULL || 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() > maxDepth)
                maxDepth = S.size();
        }
        return maxDepth;
    }
};

参考推荐：

Maximum Depth of Binary Tree

树与二叉树的深度优先与广度优先算法