[C++] Leetcode 104. Maximum Depth of Binary Tree (Hint, Solution)

Problem

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Maximum Depth of Binary Tree - LeetCode

 

 

Hint

Try using recursive approach.

 

 

Solution

To solve this problem, we can utilize a recursive approach. Let's outline the steps:

1. If the given binary tree is empty (i.e., the root is null), the depth is zero. We have reached the base case, so we return 0.
2. Otherwise, we calculate the maximum depth of the left and right subtrees recursively. We make two recursive calls, one for the left child and one for the right child.
3. We compare the depths of the left and right subtrees and return the maximum depth between them plus one. The "+1" accounts for the current node in the path.

 

 

Code

Simple

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

 

Whole Code with Test Case

// https://leetcode.com/problems/maximum-depth-of-binary-tree/
#include <iostream>
#include <algorithm>

using namespace std;


//  Definition for a binary tree node.
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };


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

int main() {
    Solution s = Solution();
    TreeNode node15(15);
    TreeNode node7(7);
    TreeNode node20(20, &node15, &node7);
    TreeNode node9(9);
    TreeNode root(3, &node9, &node20);
    cout << s.maxDepth(&root) << endl;
}

 

 

Complexity

Time

Time complexity will be O(n).

 

Space

Space complexity will be O(1).

 

 

 

Best Solution (Pinned)

class Solution {
private:
    int dfs(TreeNode* root, int level) {
        if (root == 0) return level;
        int Max = level;
        Max = max(Max, dfs(root -> left, level + 1));
        Max = max(Max, dfs(root -> right, level + 1));
        root -> left = 0;
        root -> right = 0;
        return Max;
    }
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return dfs(root, 0);
    }
};

 

 

Overall