这道题要求空间复杂度为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所指向的位置了。