这道题要求空间复杂度为O(1)，如果没有这个条件可以创建一个vector将所有结点放进去之后进行操作。
所以这道题的思路可以用一个节点来指向上一个经过的结点，用于链接两个结点。
我们创建出一个指针front，这个指针指向的是中序遍历中的指针的上一个位置，用于前后进行链接。
用递归。
遍历的结点遍历完左再向右，向右的过程中，正好到了4的位置，4的左指针指向前驱，前驱是什么都没有，所以指向空就可以了，然后让右指针指向父节点，这个时候我们并不知道父节点，那么这时可以将指针front指向这里，然后本身返回上一层访问的就是父节点（这里是6），这个时候本来是要访问右子树的，在这个过程中让front指针的右指针指向该节点，就完成了一次链接，以此循环就可以了。
最后一步退出之后front指向16的结点，该节点没有后继，所以不需要指向空指针。（这里其实随意）
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: void linked(TreeNode* root, TreeNode*& front) { if(root == nullptr) return ; linked(root->left, front); root->left = front; if(front)//如果front为空就说明不需要让front指向谁 front->right = root; front = root; linked(root->right, front); } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* front = nullptr; TreeNode* root = pRootOfTree; linked(root, front); while(root && root->left)//找到链表表头 root = root->left; return root; } };
这里的前缀结点指针front必须加一个引用，因为在递归的时候返回上一层要将front的位置也带回去，如果不带引用上一层储存的就不是当前层的front所指向的位置了。
