Problem of The Day: Longest ZigZag Path in a Binary Tree

Problem Statement

leetcode problem link

My Solution [Accepted]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        if (root == null)
            return [];
        Queue<TreeNode> queue = new Queue<TreeNode>();
        List<int> res = new List<int>();
        queue.Enqueue(root);
        while (queue.Count > 0) {
            var n = queue.Count;
            res.Add(queue.Peek().val);
            for (int i = 0; i < n; i++) {
                var curr = queue.Dequeue();
                if (curr.right != null) {
                    queue.Enqueue(curr.right);
                }
                if (curr.left != null) {
                    queue.Enqueue(curr.left);
                }
            }
        }

        return res;
    }
}

Editorial

Approach 1: BFS: Two Queues

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

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

        while next_level:
            # prepare for the next level
            curr_level = next_level
            next_level = deque()

            while curr_level:
                node = curr_level.popleft()

                # add child nodes of the current level
                # in the queue for the next level
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)

            # The current level is finished.
            # Its last element is the rightmost one.
            rightside.append(node.val)

        return rightside

Approach 2: BFS: One Queue + Sentinel

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

        queue = deque(
            [
                root,
                None,
            ]
        )
        rightside = []

        curr = root
        while queue:
            prev, curr = curr, queue.popleft()

            while curr:
                # add child nodes in the queue
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)

                prev, curr = curr, queue.popleft()

            # the current level is finished
            # and prev is its rightmost element
            rightside.append(prev.val)

            # add a sentinel to mark the end
            # of the next level
            if queue:
                queue.append(None)

        return rightside