8ms Recursive/BFS C++ Solutions


  • 12

    Well, this problem has the highest acceptance rate among all OJ problems. It has a very easy 1-line reursive solution. I am not sure whether this one can be called "DFS" so I only call it "recursive".

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

    Well, you may also solve it using a level-order traversal (BFS) with a queue.

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            int depth = 0;
            if (!root) return depth;
            queue<TreeNode*> level;
            level.push(root);
            while (!level.empty()) {
                depth++;
                int n = level.size();
                for (int i = 0; i < n; i++) {
                    TreeNode* node = level.front();
                    level.pop();
                    if (node -> left) level.push(node -> left);
                    if (node -> right) level.push(node -> right);
                }
            }
            return depth; 
        } 
    };

  • 0
    K

    Using pairs, 12ms:

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if (!root) { return 0; }
    
            int depth = 0;
            queue<std::pair<TreeNode*, int>> lst;
    
            lst.push(std::make_pair(root, 0));
            while (!lst.empty()) {
                std::pair<TreeNode*, int> curr = lst.front();
                lst.pop();
    
                TreeNode *leaf = curr.first;
                int lvl = curr.second;
    
                if (leaf) {
                    lst.push(std::make_pair(leaf->left, lvl + 1));
                    lst.push(std::make_pair(leaf->right, lvl + 1));
                    continue;
                }
    
                depth = max(depth, lvl);
            }
    
            return depth;
        }
    };

  • 0

    Hi, kkamkou. I wonder what is the advantage of using pair<TreeNode*, int> if it will slow down your code (seen from the running time)?


  • 0
    K

    none, just as a variant.


  • 0
    S

    My std::pair solution was 8ms,

    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        
        std::queue<std::pair<int, TreeNode*>> nodes; // Depth, TreeNode*
        nodes.push(std::pair<int, TreeNode*>(1, root));
        
        // Iterate through each level, adding the next depth to the queue
        int maxNodeDepth = 1;
        while (nodes.size() > 0) {
            std::pair<int, TreeNode*> pair = nodes.front();
            nodes.pop();
            auto currentDepth = pair.first;
            TreeNode* currentNode = pair.second;
            if (currentDepth > maxNodeDepth) {
                maxNodeDepth = currentDepth;
            }
            if (currentNode->left != nullptr) {
                nodes.push(std::pair<int, TreeNode*>(currentDepth+1, currentNode->left));
            }
            if (currentNode->right != nullptr) {
                nodes.push(std::pair<int, TreeNode*>(currentDepth+1, currentNode->right));
            }
        }
        
        return maxNodeDepth;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.