C# - 2 solutions BFS and DFS


  • 0

    Here are 2 solutions BFS and DFS, of the 2 DFS performs better due to the stack holding onto fewer nodes than the queue.

    here is the BFS solution (level order traversal)

        public IList<int> RightSideView(TreeNode root) 
        {
            Queue<TreeNode> queue = new Queue<TreeNode>();
            IList<int> list = new List<int>();
            if (root != null) queue.Enqueue(root);
            
            while (queue.Count > 0)
            {
                int cnt = queue.Count;
                bool first = true;
                while (cnt-- > 0)
                {
                    TreeNode node = queue.Dequeue();
                    if (first)
                    {
                        list.Add(node.val);
                        first = false;
                    }
                    
                    if (node.right != null) queue.Enqueue(node.right);
                    if (node.left != null) queue.Enqueue(node.left);
                }
            }
            
            return list;
        }
    

    Here is the DFS

        public IList<int> RightSideView(TreeNode root) 
        {
            Stack<TreeNode> stackNode = new Stack<TreeNode>();
            Stack<int> stackLevel = new Stack<int>();
            IList<int> list = new List<int>();
            
            if (root != null)
            {
                stackNode.Push(root);
                stackLevel.Push(0);
            }
            
            while (stackNode.Count > 0)
            {
                TreeNode node = stackNode.Pop();
                int level = stackLevel.Pop();
                if (list.Count == level)
                {
                    list.Add(node.val);
                }
                
                if (node.left != null) { stackNode.Push(node.left); stackLevel.Push(level+1); }
                if (node.right != null) { stackNode.Push(node.right); stackLevel.Push(level+1); }
            }
            
            return list;
        }
    

Log in to reply
 

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