ZigZag树列

Question

这个问题是在我接受的一次编码采访中提出的，它也是极客对极客的访问，https://www.geeksforgeeks.org/zigzag-tree-traversal/。

您将得到一棵二叉树，您需要按字形/蛇号顺序打印，一级从左到右，下一个级别从右到左，等等。

我只被要求想出一个解决方案--我在真正的采访中使用了一个队列和一个堆栈，当我现在使用两个堆栈对其进行编码时。

请检查代码，如果它是一个真正的面试，复杂性，编码风格，假设我有20-30分钟的代码。您可以忽略测试用例。

谢谢。

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

namespace TreeQuestions
{
    [TestClass]
    public class PrintBinaryTreeZigZag
    {

        [TestMethod]
        public void PrintBinaryTreeZigZagTest()
        {
            BinaryTree root = new BinaryTree
            {
                Value = 1,
                Left = new BinaryTree { Value = 2 },
                Right = new BinaryTree { Value = 3 }
            };
            root.Left.Left = new BinaryTree { Value = 7 };
            root.Left.Right = new BinaryTree { Value = 6 };
            root.Right.Left = new BinaryTree { Value = 5 };
            root.Right.Right = new BinaryTree { Value = 4 };
            List<int> res = PrintBinaryZigZag(root);
            List<int> expected = new List<int> { 1, 3, 2, 7, 6, 5, 4 };
            CollectionAssert.AreEqual(expected, res);

        }

        public List<int> PrintBinaryZigZag(BinaryTree root)
        {
            if (root == null)
            {
                return null;
            }
            Stack<BinaryTree> currentLevel = new Stack<BinaryTree>();
            Stack<BinaryTree> nextLevel = new Stack<BinaryTree>();
            List<int> result = new List<int>();
            currentLevel.Push(root);
            bool leftToRight = true;
            while (currentLevel.Count > 0)
            {
                BinaryTree temp = currentLevel.Peek();
                currentLevel.Pop();
                if (temp != null)
                {
                    //same as print
                    result.Add(temp.Value);

                    if (leftToRight)
                    {
                        if (temp.Left != null)
                        {
                            nextLevel.Push(temp.Left);
                        }
                        if (temp.Right != null)
                        {
                            nextLevel.Push(temp.Right);
                        }
                    }
                    else
                    {
                        if (temp.Right != null)
                        {
                            nextLevel.Push(temp.Right);
                        }
                        if (temp.Left != null)
                        {
                            nextLevel.Push(temp.Left);
                        }
                    }
                }
                if (currentLevel.Count == 0)
                {
                    leftToRight = !leftToRight;
                    Stack<BinaryTree> tempStack = currentLevel;
                    currentLevel = nextLevel;
                    nextLevel = tempStack;
                }
            }
            return result;
        }
    }
    public class BinaryTree
    {
        public BinaryTree Left { get; set; }
        public BinaryTree Right { get; set; }
        public int Value { get; set; }
    }
}

Answer 1

算法看起来不错，所以我将回顾OOP方面。

命名

1. 名为PrintBinaryZigZag的方法，但它不打印任何东西。
2. 名为BinaryTree的类实际上不是一个二叉树，它更像是一个Node。

实现与接口

您返回List<int>，但真的需要一个列表吗？

如果要返回表示二叉树的列表，则此方法的目标。

您应该能够从这个列表中添加/删除对象吗？您需要特定于列表的索引器吗？我不这样认为。在本例中，返回IEnumerable<int>。

C# details

BinaryTree temp = currentLevel.Peek();
currentLevel.Pop();

您可以简单地这样做：BinaryTree temp = currentLevel.Pop();

流

if (leftToRight)
{
    if (temp.Left != null)
    {
        nextLevel.Push(temp.Left);
    }
    if (temp.Right != null)
    {
        nextLevel.Push(temp.Right);
    }
}
else
{
    if (temp.Right != null)
    {
        nextLevel.Push(temp.Right);
    }
    if (temp.Left != null)
    {
        nextLevel.Push(temp.Left);
    }
}

我肯定有办法让这个变小。现在，这是一个可能给你一个想法，我不认为它是完美的，它是奇怪的使用一个foreach，当你只有两个元素在列表中。但是如果能给你一个让代码变小的想法。

var orderedNodes = leftToRight ? new []{ temp.Left, temp.Right } : new []{ temp.Right, temp.Left };

foreach(var node in orderedNodes.Where(n => n != null)) 
{
    nextLevel.Push(node);
}

这是：

if (currentLevel.Count == 0)
{
    leftToRight = !leftToRight;
    Stack<BinaryTree> tempStack = currentLevel;
    currentLevel = nextLevel;
    nextLevel = tempStack;
}

我认为它可能在你的while循环之外。