104. Maximum Depth of Binary Tree

leetcode easy

#csharp#easy#graph#leetcode#math#recursion#search#tree#two-pointers

Task

Дан корень бинарного дерева, верните его максимальную глубину.

Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7]

Output: 3

C# solution

matched/original

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int left_height = MaxDepth(root.left);
            int right_height = MaxDepth(root.right);
            return 1 + Math.Max(left_height, right_height);
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int left_height = MaxDepth(root.left);
            int right_height = MaxDepth(root.right);
            return 1 + max(left_height, right_height);
        }
    }
}

Java solution

matched/original

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int left_height = maxDepth(root.left);
            int right_height = maxDepth(root.right);
            return java.lang.Math.max(left_height, right_height) + 1;
        }
    }
}

JavaScript solution

matched/original

var maxDepth = function (root) {
    if (root === null) {
        return 0;
    }
    const left_height = maxDepth(root.left);
    const right_height = maxDepth(root.right);
    return 1 + Math.max(left_height, right_height);
};

Python solution

matched/original

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height) + 1

Go solution

matched/original

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left_height := maxDepth(root.Left)
    right_height := maxDepth(root.Right)
    return 1 + max(left_height, right_height)
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

1️⃣

Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2️⃣

Для данной задачи подойдет несколько способов.

3️⃣