学步园

将一棵普通二叉树转换为一棵线索二叉树（查看定义）。

详细说明：树结点除了包含left, right指针外，还包含isLeftThread和isRightThread，初始时isLeftThread和isRightThread都为false。对于left为null的结点，请将left设置为中序遍历该结点的前驱结点，并将isLeftThread设置为true。对于right为null的结点，请将right设置为中序遍历该结点的后继结点，并将isRightThread设置为true。

提示：请尝试使用非递归算法。

第一反应还是中序遍历然后递归，先忽略提示使用非递归吧。

又是对着错的测试用例然后改了下代码才A过。

/*树结点的定义(请不要在代码中定义该结构)
struct TreeNode {
  TreeNode *left, *right;
  bool isLeftThread, isRightThread;
}*/
void inorder(TreeNode* root,TreeNode*& pre,int& preNeedSet);
void convertToThreadedTree(TreeNode *root) {
	if ( !root ) 
		return;
	TreeNode* pre=NULL;
	int preNeedSet=0;
	inorder(root,pre,preNeedSet);
	if (pre&&preNeedSet )
		pre->isRightThread=true;
}
void inorder(TreeNode* root,TreeNode*& pre,int& preNeedSet)
{
	if (!root )
		return;
	inorder(root->left,pre,preNeedSet);
	if ( !root->left )
	{
		root->isLeftThread=true;
		if ( pre )
		{
			root->left = pre;
			
		}
	}
    if ( pre&&preNeedSet )
	{
		pre->isRightThread=true;
		pre->right=root;
	}
	pre=root;
	if (!root->right )
		preNeedSet=1;
    else
        preNeedSet=0;
	inorder(root->right,pre,preNeedSet);
}