199. Binary Tree Right Side View

leetcode medium

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

Task

Дано корень бинарного дерева, представьте, что вы стоите с правой стороны от него, верните значения узлов, которые вы видите, упорядоченные сверху вниз.

Пример:

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

C# solution

matched/original

public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        if (root == null) return new List<int>();
        var nextLevel = new Queue<TreeNode>();
        var rightside = new List<int>();
        nextLevel.Enqueue(root);
        while (nextLevel.Count > 0) {
            int levelSize = nextLevel.Count;
            for (int i = 0; i < levelSize; i++) {
                var node = nextLevel.Dequeue();
                if (node.left != null) nextLevel.Enqueue(node.left);
                if (node.right != null) nextLevel.Enqueue(node.right);
                if (i == levelSize - 1) rightside.Add(node.val);
            }
        }
        return rightside;
    }
}

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 vector<int> RightSideView(TreeNode root) {
        if (root == null) return new List<int>();
        var nextLevel = new queue<TreeNode>();
        var rightside = new List<int>();
        nextLevel.Enqueue(root);
        while (nextLevel.size() > 0) {
            int levelSize = nextLevel.size();
            for (int i = 0; i < levelSize; i++) {
                var node = nextLevel.Dequeue();
                if (node.left != null) nextLevel.Enqueue(node.left);
                if (node.right != null) nextLevel.Enqueue(node.right);
                if (i == levelSize - 1) rightside.push_back(node.val);
            }
        }
        return rightside;
    }
}

Java solution

matched/original

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return new ArrayList<Integer>();

        ArrayDeque<TreeNode> nextLevel = new ArrayDeque() {
            {
                offer(root);
            }
        };
        ArrayDeque<TreeNode> currLevel = new ArrayDeque();
        List<Integer> rightside = new ArrayList();

        TreeNode node = null;
        while (!nextLevel.isEmpty()) {
            currLevel = nextLevel;
            nextLevel = new ArrayDeque<>();

            while (!currLevel.isEmpty()) {
                node = currLevel.poll();

                if (node.left != null) nextLevel.offer(node.left);
                if (node.right != null) nextLevel.offer(node.right);
            }

            if (currLevel.isEmpty()) rightside.add(node.val);
        }
        return rightside;
    }
}

JavaScript solution

matched/original

class Solution {
    rightSideView(root) {
        if (root === null) return [];

        let nextLevel = [root];
        let rightside = [];

        while (nextLevel.length > 0) {
            let currLevel = nextLevel;
            nextLevel = [];

            for (let node of currLevel) {
                if (node.left !== null) nextLevel.push(node.left);
                if (node.right !== null) nextLevel.push(node.right);
            }

            rightside.push(currLevel[currLevel.length - 1].val);
        }
        return rightside;
    }
}

Python solution

matched/original

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        next_level = deque([root])
        rightside = []

        while next_level:
            curr_level = next_level
            next_level = deque()

            while curr_level:
                node = curr_level.popleft()

                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)

            rightside.append(node.val)

        return rightside

Go solution

matched/original

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    nextLevel := []*TreeNode{root}
    rightside := []int{}

    for len(nextLevel) > 0 {
        currLevel := nextLevel
        nextLevel = []*TreeNode{}

        for _, node := range currLevel {
            if node.Left != nil {
                nextLevel = append(nextLevel, node.Left)
            }
            if node.Right != nil {
                nextLevel = append(nextLevel, node.Right)
            }
        }

        rightside = append(rightside, currLevel[len(currLevel)-1].Val)
    }

    return rightside
}

Explanation

Algorithm

1️⃣

Инициализируйте список правого обзора rightside. Инициализируйте две очереди: одну для текущего уровня и одну для следующего. Добавьте корень в очередь nextLevel.

2️⃣

Пока очередь nextLevel не пуста:

Инициализируйте текущий уровень: currLevel = nextLevel и очистите очередь следующего уровня nextLevel.

Пока очередь текущего уровня не пуста:

Извлеките узел из очереди текущего уровня.

Добавьте сначала левый, а затем правый дочерний узел в очередь nextLevel.

Теперь очередь currLevel пуста, и узел, который у нас есть, является последним и составляет часть правого обзора. Добавьте его в rightside.

3️⃣

Верните rightside.

😎