昨天同事说了一道题，这道题说难也难，说简单也简单，但是细节比较麻烦，是个难题，如果这个是面试题的话，确实能够拦下很多人。

题目：有一串字符串，根据字符串生成二叉树，输入输出如下（输出是以树的形式输出）。

输入：{1}

输出：1

输入：{1{2,3}}

输出：根节点1，1的左节点为2，1的右节点为3

输入：{1{2{4},3{5,6}}}

输出：根节点1，1的左节点为2，2的左节点为4，右节点为空，1的右节点为3，3的左右节点分别为5，6。

下面是代码，慎看，并不一定是最好的，与标答还是有一定的距离的，不过效率还不错，标答就比较难理解了，过一段时间我再把标答发上来。思路不是很难，但是代码估计很难看懂：（

生成树#region 生成树

思路#region 思路

//我们遍历字符串并压入到堆里面，如{1{2{4},3}}
//我们找到}字符的位置，然后此处到前面{符号的
//字符都出栈，生成树节点，即生成了2和2的左节点
//然后我们再进栈，直到3的位置，我们再出栈，同理
//我们可以生成1，2，3这三个节点，即1左节点为2
//1的右节点为3

#endregion

Code#region Code

namespace TreeGenerator
…{
class TreeNode
…{
public char data;
public TreeNode lchild;
public TreeNode rchild;
}

class Program
…{
//一个存放字符串的栈
static Stack<char> stack;
//一个存放节点的栈
static Stack<TreeNode> stackTree;

static void Main(string[] args)
…{
stack = new Stack<char>();
stackTree = new Stack<TreeNode>();
string treecode = “{1{2,3{2,2}}}“;
GenerateNodes(treecode);
}

static void GenerateNodes(string treecode)
…{
//如果为{1}则直接生成退出
if (treecode.Length == 3)
…{
TreeNode tpnode = new TreeNode();
tpnode.data = treecode[1];
stackTree.Push(tpnode);
return;
}

//否则遍历字符串
for (int i = 0; i < treecode.Length; i++)
…{
stack.Push(treecode[i]);

//如果不是}就进栈
if (treecode[i] == ‘}‘)
…{
//否则就创建节点
PopAndCreateNode();
}
}
}

static void PopAndCreateNode()
…{
char c;
char t;
bool isAdded = false;

TreeNode farther = new TreeNode();

stack.Pop();
//创建节点
while ((c = stack.Pop()) != ‘{‘)
…{
TreeNode node = new TreeNode();
node.data = c;
node.lchild = null;
node.rchild = null;

if ((c = stack.Pop()) != ‘,‘)
…{
if (!isAdded)
…{
farther.lchild = node;
}
break;
}
else
…{
farther.rchild = node;
}
}
//如果字符串的栈不为空
if (stack.Count > 0)
…{
farther.data = stack.Pop();
//将在节点栈里面的节点组合在一起
farther = AddToNode(farther);
//这里节点组合后节点栈就为空了，再进栈
stackTree.Push(farther);
stack.Push(farther.data);
}
}

static TreeNode AddToNode(TreeNode node)
…{
int length = stackTree.Count;

while (length > 0 && stackTree.Count > 0)
…{
TreeNode tnode = stackTree.Pop();
//如果栈里面的节点的值相同就组合
if (node.rchild != null && node.rchild.data == tnode.data)
…{
node.rchild = tnode;
}
else
…{
//否则再进栈
stackTree.Push(tnode);
}

if (stackTree.Count > 0)
…{
tnode = stackTree.Pop();
if (node.lchild != null && node.lchild.data == tnode.data)
…{
node.lchild = tnode;
}
else
…{
stackTree.Push(tnode);
}
}
length–;
}

return node;
}
}
}

#endregion

#endregion

标答的技巧很巧妙，过一段时间让朋友帖上来。