3
\$\begingroup\$

Please review for performance. and also naming convention

https://leetcode.com/problems/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]
using System.Collections.Generic;
using System.Linq;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/binary-tree-level-order-traversal/
    /// </summary>
    [TestClass]
    public class BinaryTreeLevelOrderTraversalTest
    {

        //      3
        //     / \
        //    9  20
        //   /  \
        //  15   7
        [TestMethod]
        public void TreeTest()
        {
            TreeNode root = new TreeNode(3);
            root.left = new TreeNode(9);
            root.right = new TreeNode(20);
            root.left.left = new TreeNode(15);
            root.left.right = new TreeNode(7);
            IList<IList<int>> res = BinaryTreeLevelOrderTraversalClass.LevelOrder(root);
            CollectionAssert.AreEqual(res[0].ToList(), new List<int>{3});
            CollectionAssert.AreEqual(res[1].ToList(), new List<int>{9,20});
            CollectionAssert.AreEqual(res[2].ToList(), new List<int>{15,7});
        }


        [TestMethod]
        public void OneNodeTreeTest()
        {
            TreeNode root = new TreeNode(3);
            IList<IList<int>> res = BinaryTreeLevelOrderTraversalClass.LevelOrder(root);
            CollectionAssert.AreEqual(res[0].ToList(), new List<int> { 3 });
        }
    }

    public class BinaryTreeLevelOrderTraversalClass
    {
        public static IList<IList<int>> LevelOrder(TreeNode root)
        {
            List<IList<int>> res = new List<IList<int>>();
            if (root == null)
            {
                return res;
            }
            Queue<TreeNode> Q = new Queue<TreeNode>();

            Q.Enqueue(root);

            int counter = 0; // which level
            while (Q.Count > 0)
            {
                int children = Q.Count;
                res.Add(new List<int>());
                for (int i = 0; i < children; i++)
                {
                    var temp = Q.Dequeue();
                    res[counter].Add(temp.val);
                    if (temp.left != null)
                    {
                        Q.Enqueue(temp.left);
                    }
                    if (temp.right != null)
                    {
                        Q.Enqueue(temp.right);
                    }
                }
                counter++;
            }
            return res;
        }
    }

}
\$\endgroup\$
1
\$\begingroup\$

Avoid unnecessary variables

The counter variable is unnecessary. For each level, you need just a List<int> level, add the elements of the level to this list, and then add this list to res.

By eliminating this variable, you also eliminate any concerns about the correctness of res[counter].Add(temp.val);. With the code changed to level.Add(temp.val), the mental burden is reduced.

Use more descriptive names

  • res could be levels
  • temp could be node
  • LevelOrder could be GetLevels
  • BinaryTreeLevelOrderTraversalClass would be better without Class
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.