55Ⅰ.二叉树的深度

raylan.chen大约 1 分钟

先序遍历，根节点 != null 时，cou++，比较 cou >? max，大于则使用 max 记录最大深度；

随后遍历左子树，并且在递归返回时，cou--（因为此时需要遍历右子树，右子树需要依据根节点的深度来计算最大深度，不能在左子树的深度上进行叠加）；

最后，遍历右子树，并且在递归返回时，cou--。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int cou;
    int max;
    public int calculateDepth(TreeNode root) {
        // dfs
        cou = 0;
        max = 0;
        dfs(root);
        return max;
    }

    public void dfs(TreeNode root) {
        if (root == null) return;
        
        cou++;
        if (cou > max) max = cou;

        if (root.left != null) {
            dfs(root.left);
            cou--;
        }
        if (root.right != null) {
            dfs(root.right);
            cou--;
        }
    }
}

优秀题解

class Solution {
    public int calculateDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(calculateDepth(root.left), calculateDepth(root.right)) + 1;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/solutions/159058/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

非常精简的代码！

遍历左右子树，利用递归的返回值计算左右子树的深度，可以舍去 +1/-1 的流程

55Ⅰ.二叉树的深度

55Ⅰ.二叉树的深度

参考链接

个人尝试

优秀题解