递归遍历

• 中序遍历修改全局变量的指针，且不改变当前函数栈帧pRootOfTree的指针的right。
• 注意head是变化，多一个变量保存head。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	TreeNode* head1=new TreeNode(-1);
	TreeNode* head=head1;
	void InOrder(TreeNode* pRootOfTree)
	{
		if(!pRootOfTree)
		{
			return;
		}
		InOrder(pRootOfTree->left);
		//
		head->right=pRootOfTree;
		head=head->right;
		InOrder(pRootOfTree->right);

	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
    //中序遍历
	if(!pRootOfTree)
	{
		return nullptr;
	}
	InOrder(pRootOfTree);
	TreeNode* front=nullptr,*cur=head1->right,*ret=head1->right;
	while(cur)
	{
		cur->left=front;
		front=cur;
		cur=cur->right;
	}
	return ret;
	}
};

非递归遍历

• 用栈实现非递归中序遍历
• while嵌套while，边界条件是空指针

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        //非递归栈法
		stack<TreeNode*> s;
		if(!pRootOfTree)
		{
			return nullptr;
		}
		TreeNode* head=new TreeNode(-1);
		TreeNode* cur1=head;
		TreeNode* cur2=pRootOfTree;
		// s.push(pRootOfTree);
		while(s.size()||cur2)
		{
			while(cur2)
			{
				s.push(cur2);
				cur2=cur2->left;
			}
			//cur2 nullptr;
			while(!cur2&&s.size())//cur2 nullptr
			{
				cur1->right=s.top();
				cur1=cur1->right;
				cur2=s.top()->right;
				s.pop();
			}
		}
		cur1=head->right;
		TreeNode* ret=cur1;
		TreeNode* front=nullptr;
		while(cur1)
		{
			cur1->left=front;
			front=cur1;
			cur1=cur1->right;
		}
		return ret;
    }
};