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.

http://www.lintcode.com/en/problem/maximum-depth-of-binary-tree/

Discussion

递归很简单，左右子树的最大depth加1. 非递归的写法就是level order traversal。

Solution

递归。O(n) runtime, O(log n) space

Assume that n is the total number of nodes in the tree. The runtime complexity is O(n) because it traverse each node exactly once. As the maximum depth of a binary tree is O(log n), the extra space cost is O(log n) due to the extra stack space used by the recursion.

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxDepth(TreeNode *root) {
        // write your code here
        if(root == NULL) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

level order traversal. O(n) runtime, O(n) space.

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxDepth(TreeNode *root) {
        // write your code here
        if(root == NULL) return 0;
        queue<TreeNode*> que;
        int ret=0;
        que.push(root);
        while (!que.empty()) {
            int sz = que.size();//que里存的总是当前level的所有节点。
            for(int i=0; i<sz; i++) {//pop sz次，也就是把之前level清空
                TreeNode *tmp = que.front();
                que.pop();
                if(tmp->left != NULL) {
                    que.push(tmp->left);
                }
                if(tmp->right != NULL) {
                    que.push(tmp->right);
                }
            }
            ret++;
        }
        return ret;
    }
};