力扣 104.二叉树的最大深度

Question

题目是求二叉树的深度，结果一直是depth==0。任何人都可以帮助找出我的代码哪里出了问题吗？非常感谢！

问题是：** 给定二叉树的根，return 它的最大深度。二叉树的最大深度是从根节点到最远叶节点的最长路径上的节点数。**

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

这个算法可以认为是下面的递归定义

设T为有根二叉树。 MaxDepth(T) = 0 如果 T 为空。那么，如果T不是叶子，MaxDepth(T) = 1 + max(MaxDepth(T_L), MaxDepth(T_R))其中T_L和T_R分别是左右子树。

您似乎已经从您的代码中认识到了这一事实，这很棒。您正在执行 DFS 并在执行遍历时跟踪深度，return 计算每个阶段的深度。（我对你在这条线上使用的逻辑有点怀疑 c-=c; 但这不是大问题）。

你的算法的主要问题似乎是你没有return在任何时候从你的 DFS 中获取一个值。您只需对跟踪每个点深度的树执行 DFS 搜索，并在通过递归树向上移动时进行减法。如果您通过引用传递参数，这可能没问题，但除非我弄错了，否则这是 C++，并且您是通过值传递参数。因此，当您在函数调用中赋值时，您实际上并没有访问同一个变量，只是它的一个副本，不会传播到您的调用函数。

下面是一些工作的 C++ 代码，其中一种方法是：

#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);
}

此代码将 return 1 用于单个根节点，0 用于空树。

要通过引用传递，需要在参数名称前放置一个&。希望这个 link 能帮助您理解参数传递。 https://www.cs.fsu.edu/~myers/c++/notes/references.html

力扣 104.二叉树的最大深度

leetcode104. Maximum Depth of Binary Tree

tree

depth-first-search