📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5731| 回复: 15
跳转到指定楼层
上一主题 下一主题
收起左侧

Facebook :Convert a BST to linked list

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).

use leftChild as "prev"

use rightChild as "next"

上一篇:C和C++的编码规范
下一篇:Google : Write a function to reverse digits of an integer
推荐
chancidy 2017-9-24 00:29:25 | 只看该作者
全局:
涉入如有 发表于 2017-9-22 05:24
挖个坟。。这题居然从11年出到17年。。

其实10年就有了,http://articles.leetcode.com/convert-binary-search-tree-bst-to/
回复

使用道具 举报

全局:
chancidy 发表于 2017-9-24 00:29
其实10年就有了,http://articles.leetcode.com/convert-binary-search-tree-bst-to/

你是不是收藏了这个帖子
回复

使用道具 举报

全局:
挖个坟。。这题居然从11年出到17年。。
回复

使用道具 举报

🔗
wwwyhx 2011-10-19 08:12:36 | 只看该作者
全局:
两个字 : 递归
回复

使用道具 举报

🔗
darksteel 2011-10-19 09:17:40 | 只看该作者
全局:
回复 2# wwwyhx
这题你以前发过吧?我好像见过。
思路是递归确实没错,先处理左子树,然后把节点本身加进去,然后再处理右子树。有一个要注意的地方就是初始可以传个哨兵节点作为链表的头,最后得到链表的尾,再通过这个哨兵把头尾连接起来。
回复

使用道具 举报

🔗
wwwyhx 2011-10-19 10:29:39 | 只看该作者
全局:
回复  wwwyhx
这题你以前发过吧?我好像见过。
思路是递归确实没错,先处理左子树,然后把节点本身加进去,然后再处理右子树。有一个要注意的地方就是初始可以传个哨兵节点作为链表的头,最后得到链表的尾,再通过这个哨兵把头尾连接起来。
darksteel 发表于 2011-10-19 09:17



    这个以前发过, 就在版上
回复

使用道具 举报

🔗
wwwyhx 2011-10-21 05:12:37 | 只看该作者
全局:

  1. void _inner_trans(NODE* pNode, NODE*& pHead, NODE*& pTail)
  2. {
  3.         pHead = NULL;
  4.         pTail = NULL;

  5.         if (NULL == pNode)
  6.                 return;
  7.        
  8.         NODE* pH, *pT;
  9.         _inner_trans(pNode->pLft, pH, pT);
  10.        
  11.         if (NULL == pT)
  12.                 pHead = pNode;
  13.         else
  14.         {
  15.                 pT->pRgt = pNode;
  16.                 pNode->pLft = pT;
  17.                 pHead = pH;
  18.         }

  19.         _inner_trans(pNode->pRgt, pH, pT);
  20.         if (NULL == pH)
  21.                 pTail = pNode;
  22.         else
  23.         {
  24.                 pH->pLft = pNode;
  25.                 pNode->pRgt = pH;
  26.                 pTail = pT;
  27.         }
  28. }

  29. NODE* TransToDBLink(NODE* pRoot)
  30. {
  31.         assert(pRoot);

  32.         NODE* pHead, *pTail;
  33.         _inner_trans(pRoot, pHead, pTail);

  34.         return pHead;
  35. }
复制代码
回复

使用道具 举报

🔗
imwmwm 2011-10-23 14:26:11 | 只看该作者
全局:
就是前序遍历吧...
话说这学期算法作业第二个是double linked list 第三个刚做完的就是BST/AVL..
回复

使用道具 举报

🔗
nooneknow 2011-10-24 04:48:45 | 只看该作者
全局:
就是前序遍历吧...
话说这学期算法作业第二个是double linked list 第三个刚做完的就是BST/AVL..
imwmwm 发表于 2011-10-23 14:26


显然不是。
应该是中序遍历。这样没处理到的node还能找得到。
回复

使用道具 举报

🔗
nooneknow 2011-10-24 04:55:23 | 只看该作者
全局:
wwwyhx 发表于 2011-10-21 05:12


感觉没这么复杂。java写过一次。参数有root跟prev就够了。prev第一次传进去相当于个哨兵。

        static void change(TreeNode r, ArrayList<TreeNode> prev){
                if(r == null) return; //base

                change(r.left, prev); //left subtree

                TreeNode previous = prev.get(0); //change root
                previous.right = r;
                r.left = previous;
                previous = r;
                prev.set(0, previous);

                change(r.right, prev); //right subtree
        }
回复

使用道具 举报

🔗
wwwyhx 2011-10-24 06:50:19 | 只看该作者
全局:
感觉没这么复杂。java写过一次。参数有root跟prev就够了。prev第一次传进去相当于个哨兵。

        static void change(TreeNode r, ArrayList prev){
                if(r == null) return; //base

                change(r.left, prev); //left subtree

                TreeNode previous = prev.get(0); //change root
                previous.right = r;
                r.left = previous;
                previous = r;
                prev.set(0, previous);

                change(r.right, prev); //right subtree
        }
nooneknow 发表于 2011-10-24 04:55


恩 中序遍历就可以了
回复

使用道具 举报

🔗
wwwyhx 2011-10-24 07:17:17 | 只看该作者
全局:
中序遍历

  1. void _inner_trans2(NODE* pNode, NODE*& pPrev, NODE*& pHeader)
  2. {
  3.         if (NULL == pNode)
  4.                 return;

  5.         _inner_trans2(pNode->pLft, pPrev, pHeader);

  6.         pNode->pLft = pPrev;
  7.         if (pPrev != NULL)
  8.                 pPrev->pRgt = pNode;
  9.         else
  10.                 pHeader = pNode;

  11.         pPrev = pNode;

  12.         _inner_trans2(pNode->pRgt, pPrev, pHeader);
  13. }

  14. NODE* TransToDBLink2(NODE* pRoot)
  15. {
  16.         assert(pRoot);

  17.         NODE* pPrev = NULL;
  18.         NODE* pHeader = NULL;
  19.         _inner_trans2(pRoot, pPrev, pHeader);
  20.         if (NULL != pPrev)
  21.                 pPrev->pRgt = NULL;

  22.         return pHeader;
  23. }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表