Solution using a queue to store each level of the Tree


  • 0
    D
            /// <summary>
        /// right view of the BT
        ///     1
        ///    / \
        ///   2   3
        ///  /
        /// 4
        /// return should be 1->3->4
        /// solution:
        /// iterate through each level of the BT
        /// put each right most element into the return arraylist
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<int> RightSideView(TreeNode root)
        {
            IList<int> ret = new List<int>();//return value
            Queue<TreeNode> queue = new Queue<TreeNode>();
            if (root == null) return ret;
            queue.Enqueue(root);//put root into the queue
            while (queue.Count != 0)
            {
                int count = queue.Count;//record current queue size(it is actually the size of each level of the Tree)
                for (int i = 1; i <= count; i++)
                {
                    if (i == count)//when we reach the right most element, add it into "ret"
                    {
                        ret.Add(queue.Peek().val);
                    }
                    //put each element's left and right child into the Queue
                    if (queue.Peek().left != null)
                    {
                        queue.Enqueue(queue.Peek().left);
                    }
                    if (queue.Peek().right != null)
                    {
                        queue.Enqueue(queue.Peek().right);
                    }
                    queue.Dequeue();//remove the current element from our Queue
                }
            }
            return ret;
        }

  • 0
    T

    If you Dequeue() the elem anyway why are you peeking at it repeatedly? Just store it in a variable: TreeNode node = queue.Dequeue() and use that.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.