leetcode104. Maximum Depth of Binary Tree

Question

the question is to find the depth of a binary tree, but the result has always been depth==0. can anyone help find out where went wrong with my code? thanks a lot!

the question is:** Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.**

public:
    void dfs(TreeNode* root, int depth,int c){
        c++;
        if(root->left==nullptr and root->right==nullptr){
            if (depth<=c){
                depth=c;
            }
        }
        else if (root->left !=nullptr or root->right!=nullptr){
            dfs(root->left,depth,c);
            dfs(root->right,depth,c);
        }
        c-=c;
    }
    int maxDepth(TreeNode* root) {
        int depth=0;
        int c=0;
        dfs(root,depth,c);
        
        return depth;
    }
}; 

Answer 1

The algorithm for this can be thought of as the following recursive definition

Let T be a rooted binary tree. MaxDepth(T) = 0 if T is empty. Then, if T is not a leaf, MaxDepth(T) = 1 + max(MaxDepth(T_L), MaxDepth(T_R)) where T_L and T_R are the left and right sub-trees respectively.

You seem to have recognised this fact from your code which is great. You are performing a DFS and tracking the depth as you perform your traversal, returning the depth at each stage. (I'm a little iffy about the logic you are using on this line c-=c; but that's not the big issue).

The main issue with your algorithm it seems is that you aren't returning a value at any point from your DFS. You're simply performing a DFS search of the tree tracking the depth at each point and subtracting as you move back up through the recursion tree. This may be fine if you were passing arguments by reference, but unless I am mistaken, this is C++ and you are passing the arguments by value. Therefore, when you are assigning values in your function calls, you are not actually accessing the same variable, simply a copy of it that does not propagate to your calling function.

Some working C++ code is below of one method for doing it:

#include <algorithm>

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;

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

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

This code will return 1 for a single root node and 0 for an empty tree.

To pass by reference, one needs to put an & before the argument name. Hopefully, this link will assist in your understanding of argument passing. https://www.cs.fsu.edu/~myers/c++/notes/references.html