频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
lintcode将二叉树拆成链表
2017-04-19 10:34:40         来源:xspyzm的博客  
收藏   我要投稿

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);
}
}

这题思路很奇特,很难想到,关键节点的保存都恰到好处。

点击复制链接 与好友分享!回本站首页
上一篇:分布式系统中的一致性协议之两阶段提交协议
下一篇:最大字串和问题
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站