lintcode将二叉树拆成链表:将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说,用二叉树的right指针,来表示链表中的next指针。
不要忘记将左儿子标记为 null,否则你可能会得到空间溢出或是时间溢出。
您在真实的面试中是否遇到过这个题? Yes 样例1 \ 1 2 / \ \ 2 5 => 3 / \ \ \ 3 4 6 4 \ 5 \ 6
2.思路:
若根节点不为空,先把左右孩子保存到新定义节点中,若左孩子存在,把左孩子赋空值,右孩子指向左孩子,再利用while循环到左子树的最右节点,然后使该节点的右孩子指向原根节点的右孩子,对原根节点的左右孩子递归调用原函数
3.代码:
void flatten(TreeNode *root) { if(root) { TreeNode* p = root; TreeNode* left = root->left; TreeNode* right = root->right; if (left) { p = root->left; while (p->right) { p = p->right; } root->left = NULL; root->right = left; p->right = right; } flatten(root->left); flatten(root->right); } }
这题思路很奇特,很难想到,关键节点的保存都恰到好处。