102. Binary Tree Level Order Traversal

leetcode medium

#csharp#leetcode#medium#recursion#tree#two-pointers

Task

Дан корень бинарного дерева. Верните обход узлов дерева по уровням (то есть слева направо, уровень за уровнем).

Пример:

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

Output: [[3],[9,20],[15,7]]

C# solution

matched/original

public class Solution {
    IList<IList<int>> levels = new List<IList<int>>();
    public void Helper(TreeNode node, int level) {
        if (levels.Count == level)
            levels.Add(new List<int>());
        levels[level].Add(node.val);
        if (node.left != null)
            Helper(node.left, level + 1);
        if (node.right != null)
            Helper(node.right, level + 1);
    }
    public IList<IList<int>> LevelOrder(TreeNode root) {
        if (root == null)
            return levels;
        Helper(root, 0);
        return levels;
    }
}

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:
    IList<vector<int>> levels = new List<vector<int>>();
    public void Helper(TreeNode node, int level) {
        if (levels.size() == level)
            levels.push_back(new List<int>());
        levels[level].push_back(node.val);
        if (node.left != null)
            Helper(node.left, level + 1);
        if (node.right != null)
            Helper(node.right, level + 1);
    }
    public IList<vector<int>> LevelOrder(TreeNode root) {
        if (root == null)
            return levels;
        Helper(root, 0);
        return levels;
    }
}

Java solution

matched/original

class Solution {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();

    public void helper(TreeNode node, int level) {
        if (levels.size() == level) levels.add(new ArrayList<Integer>());

        levels.get(level).add(node.val);
        if (node.left != null) helper(node.left, level + 1);
        if (node.right != null) helper(node.right, level + 1);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return levels;
        helper(root, 0);
        return levels;
    }
}

JavaScript solution

matched/original

var levelOrder = function (root) {
    let levels = [];
    function helper(node, level) {
        if (levels.length === level) levels.push([]);
        levels[level].push(node.val);
        if (node.left !== null) helper(node.left, level + 1);
        if (node.right !== null) helper(node.right, level + 1);
    }
    if (root !== null) helper(root, 0);
    return levels;
};

Python solution

matched/original

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = []
        if not root:
            return levels

        def helper(node: TreeNode, level: int) -> None:
            if len(levels) == level:
                levels.append([])

            levels[level].append(node.val)

            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)

        helper(root, 0)
        return levels

Go solution

matched/original

func levelOrder(root *TreeNode) [][]int {
    levels := [][]int{}
    var helper func(*TreeNode, int)
    helper = func(node *TreeNode, level int) {
        if len(levels) == level {
            levels = append(levels, []int{})
        }
        levels[level] = append(levels[level], node.Val)
        if node.Left != nil {
            helper(node.Left, level+1)
        }
        if node.Right != nil {
            helper(node.Right, level+1)
        }
    }
    if root != nil {
        helper(root, 0)
    }
    return levels
}

Explanation

Algorithm

1️⃣

Самый простой способ решения задачи — использование рекурсии. Сначала убедимся, что дерево не пустое, а затем рекурсивно вызовем функцию helper(node, level), которая принимает текущий узел и его уровень в качестве аргументов.

2️⃣

Эта функция выполняет следующее:

Выходной список здесь называется levels, и, таким образом, текущий уровень — это просто длина этого списка len(levels). Сравниваем номер текущего уровня len(levels) с уровнем узла level. Если вы все еще на предыдущем уровне, добавьте новый, добавив новый список в levels.

3️⃣

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

Рекурсивно обработайте дочерние узлы, если они не равны None: helper(node.left / node.right, level + 1).

😎