leetcode114.二叉树转为链表
//二叉树转链表
//思路:每次找到根结点上左子树上最右边的结点ltemp，将此时的根结点的右子树接到上面去，
根结点左移，如果根结点左子树为空，但是右子树不为空，就右移，重复上面步骤，否则就退出
void flattern(TreeNode *root)
{
if (!root)
{
return;
}
TreeNode *cur = root;
TreeNode *rtemp = root; //指向右结点
TreeNode *ltemp = root; //指向左结点
while (cur->left || cur->right)
{
if (!cur->left) //左结点为空，就直接右移
{
cur = cur->right;
continue;
}
//断开右子树结点，把左子树接到右子树上
rtemp = cur->right;
ltemp = cur->left;
cur->right = ltemp;
//记得要将左子树置为空
cur->left = nullptr;
//找到此时右子树上最后的一个结点
while (ltemp->right)
{
ltemp = ltemp->right;
}
ltemp->right = rtemp;
cur = cur->right;
}
return;
}
查看30道真题和解析
