昨天晚上跟一家公司进行远程视频二面，面试官上来先扔过来一道编程题，要求在文档中手撸代码，不能用IDE编码。
一开始没想好，思路有问题，做到最后发现行不通，于是挂了。。。。。
第二天到公司静下心来整理了一下思路，写出来了。 做下记录，算是给自己提个醒，以后遇事要沉着冷静~~~~~
题目如下：
首先，观察题目。 第一个图代表的是二叉树， 第二个图代表的是那种某个节点的左子树指向右子树的情况，第三个图代表了某个节点的子节点指向父节点或者指向祖辈节点的情况
注意我标红的部分，这三个图要表达的是它们各自代表一类情况，而非仅仅是图中的这一种情形，所以你的程序逻辑要考虑周全
我们先来分析，按照二叉树的先序遍历规则（根->左->右）, 图一的遍历顺序应该是 ABDECF，图二的遍历规则应该是（假如也按照二叉树规则来遍历）ABDCFCF，图三的遍历顺序是ABDBDBDBD......
通过以上分析可以知道，图一的各个节点只会遍历一次； 图二的某些节点，会被遍历两次； 而图三的某几个节点，会形成一个死循环，一直遍历下去。。。
那么，这道题的答案就呼之欲出了：
1. 写一个递归程序，从A节点开始，把树遍历一次。
2. 遍历过程中，记录每个节点经过的次数
3. 如果各个节点只经历了一次，那就是tree；如果存在经历了两次的节点，并且没有经历三次的节点，就是no-tree； 如果存在经历了三次的节点，就是circle.
4. 注意，图三的情况特殊，因为是个死循环，要考虑何时退出递归函数、如何才能正常的退出递归函数，递归函数的退出方法，是个坑，不小心就会出错
代码如下：
1.定义TreeNode类型
public class TreeNode
{
/// <summary>
/// 节点的唯一ID，不重复
/// </summary>
public int nodeId { get; set; }
/// <summary>
/// 节点的名称，可能会出现重名，需要注意
/// </summary>
public string nodeName { get; set; }
/// <summary>
/// 当前节点的子节点
/// </summary>
public List<TreeNode> nextNodes { get; set; }
}
2. 定义TreeData类型
public enum TreeType
{
Tree,
NoTree,
Circle
}
//根据传入的类型，构造树结构的数据
public class TreeData
{
public TreeNode root { get; }
public TreeData(TreeType treeType)
{
if (treeType == TreeType.Tree)
{
TreeNode nodeD = new TreeNode();
nodeD.nodeId = 4;
nodeD.nodeName = "节点D";
nodeD.nextNodes = null;
TreeNode nodeE = new TreeNode();
nodeE.nodeId = 5;
nodeE.nodeName = "节点E";
nodeE.nextNodes = null;
TreeNode nodeF = new TreeNode();
nodeF.nodeId = 6;
nodeF.nodeName = "节点F";
nodeF.nextNodes = null;
TreeNode nodeC = new TreeNode();
nodeC.nodeName = "节点C";
nodeC.nodeId = 3;
nodeC.nextNodes = new List<TreeNode> { nodeF };
TreeNode nodeB = new TreeNode();
nodeB.nodeId = 2;
nodeB.nodeName = "节点B";
nodeB.nextNodes = new List<TreeNode> { nodeD, nodeE };
TreeNode nodeA = new TreeNode();
nodeA.nodeId = 1;
nodeA.nodeName = "节点A";
nodeA.nextNodes = new List<TreeNode> { nodeB, nodeC };
root = nodeA;
}
else if (treeType == TreeType.NoTree)
{
TreeNode nodeD = new TreeNode();
nodeD.nodeId = 4;
nodeD.nodeName = "节点D";
nodeD.nextNodes = null;
TreeNode nodeE = new TreeNode();
nodeE.nodeId = 5;
nodeE.nodeName = "节点E";
nodeE.nextNodes = null;
TreeNode nodeF = new TreeNode();
nodeF.nodeId = 6;
nodeF.nodeName = "节点F";
nodeF.nextNodes = null;
TreeNode nodeC = new TreeNode();
nodeC.nodeId = 3;
nodeC.nodeName = "节点C";
nodeC.nextNodes = new List<TreeNode> { nodeF };
TreeNode nodeB = new TreeNode();
nodeB.nodeName = "节点B";
nodeB.nodeId = 2;
nodeB.nextNodes = new List<TreeNode> { nodeD, nodeC };
TreeNode nodeA = new TreeNode();
nodeA.nodeId = 1;
nodeA.nodeName = "节点A";
nodeA.nextNodes = new List<TreeNode> { nodeB, nodeC };
root = nodeA;
}
else
{
TreeNode nodeD = new TreeNode();
TreeNode nodeB = new TreeNode();
nodeD.nodeId = 4;
nodeD.nodeName = "节点D";
nodeD.nextNodes = new List<TreeNode> { nodeB };
nodeB.nodeName = "节点B";
nodeB.nodeId = 2;
nodeB.nextNodes = new List<TreeNode> { nodeD };
TreeNode nodeE = new TreeNode();
nodeE.nodeId = 5;
nodeE.nodeName = "节点E";
nodeE.nextNodes = null;
TreeNode nodeF = new TreeNode();
nodeF.nodeId = 6;
nodeF.nodeName = "节点F";
nodeF.nextNodes = null;
TreeNode nodeC = new TreeNode();
nodeC.nodeId = 3;
nodeC.nodeName = "节点C";
nodeC.nextNodes = new List<TreeNode> { nodeF };
TreeNode nodeA = new TreeNode();
nodeA.nodeId = 1;
nodeA.nodeName = "节点A";
nodeA.nextNodes = new List<TreeNode> { nodeB, nodeC };
root = nodeA;
}
}
}
3. 在Program.cs中定义递归函数
public static void JudgeTreeType(TreeNode root)
{
//需要退出递归时，修改标志位的状态，递归会层层退出
if (needStop)
{
return;
}
else
{
if (root != null && root.nextNodes != null)
{
if (logDic.Keys.Contains(root.nodeId))
{
//如果节点root存在，累加一
logDic[root.nodeId] = logDic[root.nodeId] + 1;
}
else
{
//如果不存在，添加到集合中
logDic.Add(root.nodeId, 1);
}
//判定是否存在某个节点出现过次数3的情况
var hasThree = logDic.ContainsValue(3);
if (hasThree)
{
needStop = true;
}
foreach (var node in root.nextNodes)
{
JudgeTreeType(node);
}
}
}
}
4. 定义变量，记录每个节点经过的次数
//定义数据集，记录每个node被经过的次数
static Dictionary<int, int> logDic = new Dictionary<int, int>();
//注意，递归函数是层层调用的，想要在某一层让整个递归程序退出循环
//单纯用return方法是行不通的,return只是跳出了当前层的循环
//想要退出递归，需要定义一个全局变量，通过变量控制层层退出
static bool needStop = false;
5. main函数调用
static void Main(string[] args)
{
//构造root节点数据
JudgeTreeType(new TreeData(TreeType.Tree).root);
//判定树是哪种树
var hasThree = logDic.ContainsValue(3);
var hasTwo = logDic.ContainsValue(2);
if (hasThree)
{
Console.WriteLine("circle");
}
else if (!hasThree && hasTwo)
{
Console.WriteLine("no-tree");
}
else
{
Console.WriteLine("tree");
}
Console.ReadLine();
}
其实整个程序很简单，需要特别注意的是递归函数的退出方法。
仅仅在某一层递归循环中去return是无法真正退出整个递归的，它只是退出了本层递归。
想要退出整个递归，需要定义一个全局变量，通过它来控制后续递归的执行！！！
另外一个难点就是不让用IDE进行编写，必须在文档上手写代码，这对编程习惯和编码能力是个考验
源码附上：