DarkYellowCat's Blog

分享技术与思考

0%

'二叉树的最大深度'

发表于 更新于 分类于

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1.自顶向下

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null && root.right == null) return 1;
        else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

2.自底向上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
    int ans = 0;

    private void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (root.left == null && root.right == null){
            ans = Math.max(ans, depth);
        }
        dfs(root.left, depth);
        dfs(root.right, depth);
    }

    public int maxDepth(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)