二叉树转换为双向链表（后序遍历）

#include <iostream>

using namespace std;

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int v = 0, TreeNode *l = nullptr, TreeNode *r = nullptr) : val(v), left(l), right(r) {}
};

pair<TreeNode *, TreeNode *> convert(TreeNode *root)
{
	if (!root) return make_pair(nullptr, nullptr);

	TreeNode *left = nullptr, *right = nullptr;
	auto pl = convert(root->left);
	auto pr = convert(root->right);
	if (pl.second)
	{
		root->left = pl.second;
		pl.second->right = root;
		left = pl.first;
	}
	else
	{
		root->left = nullptr;
		left = root;
	}
	if (pr.first)
	{
		root->right = pr.first;
		pr.first->left = root;
		right = pr.second;
	}
	else
	{
		root->right = nullptr;
		right = root;
	}
	return make_pair(left, right);
}

TreeNode *convert2list(TreeNode *root)
{
	return convert(root).first;
}

void output_tree(TreeNode *r)
{
	if (!r) return;
	output_tree(r->left);
	cout << r->val << " ";
	output_tree(r->right);
}

void output_list(TreeNode *head)
{
	TreeNode *ph = head;
	for (; ph; ph = ph->right) cout << ph->val << " ";
	cout << endl;
}

int main()
{
	TreeNode n4(4), n8(8), n6(6, &n4, &n8), n12(12), n16(16), n14(14, &n12, &n16), n10(10, &n6, &n14);
	output_tree(&n10);
	cout << endl;

	TreeNode *head = convert2list(&n10);
	output_list(head);

	return 0;
}