欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

已知前序和中序求后序

程序员文章站 2022-05-19 20:56:24
...

1

public TreeNode createTree(String preOrder,String inOrder)
{
	if(preOrder.isEmpty())
	{
		return null;
	}
	
	char rootValue = preOrder.charAt(0);
	int rootIndex = inOrder.indexOf(rootValue);
	
	TreeNode root = new TreeNode(rootValue);
	
	root.setLeft(
		createTree(
			preOrder.substring(1,1+rootIndex),
			inOrder.substring(0,rootIndex)
		)
	);
	
	root.setRight(
		createTree(
			preOrder.substring(1+rootIndex),
			inOrder.substring(1+rootIndex)
		)
	);
	
	return root;
}

2

public String postOrder(String preOrder , String inOrder)
{
	if(preOrder.isEmpty())
	{
		return "";
	}
	
	char rootValue = preOrder.charAt(0);
	int rootIndex = inOrder.indexOf(rootValue);
	
	return preOrder(
		preOrder.substring(1,1+rootIndex),
		inOrder.substring(0,rootIndex)
	)+preOrder(
		preOrder.substring(1+rootIndex),
		inOrder.substring(1+rootIndex)
	)+rootValue;
	
}