programming challenge – LeetCode: Binary Tree Level Order Traversal C #

Please check for performance. and also naming convention

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

Given a binary tree, it returns the level order path of its nodes & # 39;
values. (that is, 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
{
    /// 
    /// https://leetcode.com/problems/binary-tree-level-order-traversal/
    /// 
    (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> res = BinaryTreeLevelOrderTraversalClass.LevelOrder(root);
            CollectionAssert.AreEqual(res(0).ToList(), new List{3});
            CollectionAssert.AreEqual(res(1).ToList(), new List{9,20});
            CollectionAssert.AreEqual(res(2).ToList(), new List{15,7});
        }


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

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

            Q.Enqueue(root);

            int counter = 0; // which level
            while (Q.Count > 0)
            {
                int children = Q.Count;
                res.Add(new List());
                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;
        }
    }

}

interview questions – leecode: N-ary Tree Level Order Traversal C #

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

Given an n-ary tree, it returns the order of transverse level to the values ​​of its nodes. (that is, from left to right, level by level).

For example, given a 3-ary tree:

enter the description of the image here

We must return your cross-level order:

[
1,
[3,2,4],
[5,6]
]

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Please comment on the complexity of space and time.
Thank you.

using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

Namespace GraphsQuestions
{
/// 
    /// https://leetcode.com/problems/n-ary-tree-level-order-traversal/
/// 

    [TestClass]
    
    
    
    public class N_aryTreeLevelOrderTraversal
{
        [TestMethod]
        public void N_aryTreeLevelOrderTraversalTest ()
{
List node3 = new list();
node3.Add (new node (5, null));
node3.Add (new node (6, null));

List node1 = new list();
node1.Add (new node (3, node3));
node1.Add (new node (2, null));
node1.Add (new node (4, null));

Root node = new node (1, node1);
var result = LevelOrder (root);
IList <IList> expected = new List <IList> ();
expected.Add (new list{one});
expected.Add (new list{3,2,4});
expected.Add (new list{5,6});

for (int i = 0; i <3; i ++)
{
CollectionAssert.AreEqual (expected[i].ToArray (), result[i].ToArray ());
}

}
Public IList <IList> LevelOrder (node ​​root)
{
IList <IList> result = new List <IList> ();
Tail Q = new queue();
if (root == null)
{
return result
}

Q.Enqueue (root);

while (Q.Count> 0)
{
List currentLevel = new list();
int qSize = Q.Count;
for (int i = 0; i <qSize; i ++)
{
var curr = Q.Dequeue ();
currentLevel.Add (curr.val);
if (curr.children! = null)
{
foreach (var child in curr.children)
{
Q.Enqueue (child);
}
}
}
result.Add (currentLevel);
}
return result
}
}
}

Python – Traversal Camino Único

I got this problem during a simulated interview, and I would like to get a code review for the tracking solution.

# Example: matrix = [[0,0,0,0],
#                     [0,0,0,0],
#                     [0,0,0,0]]#
# robotPaths (array) = 38
#
#
# matrix = [[0,0,0],
#                     [0,0,0]]#
# robotPaths (array) = 4



# Note: From any point, you can travel in the four cardinal directions. I decided to take a backward approach to solve this problem.
#           (North South East West). A road is valid while traveling.
# from the upper left corner to the lower right corner, it's not
# outside the matrix, and does not back off on itself


def robot_paths (array):
num_of_rows = len (matrix)
num_of_cols = len (matrix[0])

Def traversal (row, col):
num_of_rows not local
num_of_cols not local
# is row and column within the limits
yes row < 0 or row >= num_of_rows or col < 0 or col >= num_of_cols:
return 0

# has row, col has already been visited
if the matrix[row][col]    == 1:
return 0

# is the row, col the destination?
if the row == num_of_rows - 1 and col == num_of_cols - 1:
return 1

# coordinate mark as visited
matrix[row][col]    = 1

# initialize sum of total unique routes to finish from that coordinate
s = transversal (row, col + 1) + transversal (row + 1, col) + transversal (row - 1, col) + transversal (row, col - 1)

# recoil; Mark the coordinates as not visited so they can be
# used in another way
matrix[row][col]    = 0

returns

Return trip (0, 0)

Traversal of the graph – Minimum distance of the Dijkstra expansion shaft

I would like to build a minimum distance expansion tree (Dijkstra) for the following graph:

enter the description of the image here

MDST: {(a, c), (c, h), (c, f), (a, d), (h, g), (a, b), (d, e), (h, j) , (h, i), (j, k), (e, m), (i, l)}

enter the description of the image here

Is my understanding correct? The total cost would be 49 (sum of the distance from the root for each node).

Traversal of the graph: DFS and BFS expansion trees

You can build a DFS spanning tree or a BFS spanning tree in many ways. It could require that the next advantage be traversed, it should be the cheapest available, if that helps you in some way or if you just want to do it. While you are using DFS or BFS, you will end up with an expansion tree.

However, if you want to always traverse the next cheapest edge among all possible options, "Queue: a c d b e h h k k i j k k" for BFS should be "Queue: a c d b e h k k i j l l", which is a supposed typo.

"Is this an MCST?" No, neither is a minimum-cost expansion tree, commonly referred to as a minimum expansion tree (MST). The DFS expansion tree, {(a, c), (c, h), (h, g), (g, f), (f, b), (b, k), (k, j), ( j, i), (i, l), (l, m), (m, e), (e, d)} could have a lower cost if (g, f) is replaced by (c, f). The BFS expansion tree, {(a, c), (a, d), (a, b), (a, e), (c, f), (c, h), (b, g), ( b, k), (e, m), (h, j), (k, l)} could have a lower cost if (b, g) is replaced by (h, g). As you can see, there is no guarantee that an MST can be obtained if you use a DFS or BFS.

In fact, for this particular graph, no matter how you perform BFS or DFS, you will not end up with an MST.