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

Microsoft : 不用额外空间,链接二叉树同一层的每个node

全局:

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

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

x
比如:
           0
       1       2
   3      4         5
      6          7

1->2
3->4->5
6->7

参考数据结构:
struct TREE_NODE
{
        TREE_NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL), pSib(NULL)
        {}

        int nVal;
        TREE_NODE* pLft;
        TREE_NODE* pRgt;
        TREE_NODE* pSib;
};

上一篇:Google/Baidu : Find pervert pairs
下一篇:Google : 计算a[0]*a[1]*...*a[n-1]/a[i]
🔗
 楼主| wwwyhx 2011-5-1 23:42:45 | 只看该作者
全局:
回复 1# wwwyhx


    坐等解答,最好给个为代码啥的
回复

使用道具 举报

🔗
Etrnls 2011-5-2 00:09:06 | 只看该作者
全局:
for each node
    if I have right node
        my left's sib = my right ( if I have left node)
        my right's sib = find_next(this)
    else
        my left's sib = find_next(this)

find_next(node)
    go along sib list of me
        if has left return left
        if has right return right
    return null

评分

参与人数 1大米 +45 收起 理由
wwwyhx + 45

查看全部评分

回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-2 01:38:39 | 只看该作者
全局:
for each node
    if I have right node
        my left's sib = my right ( if I have left node)
        my right's sib = find_next(this)
    else
        my left's sib = find_next(this)

find_next(node)
    go along sib list of me
        if has left return left
        if has right return right
    return null
Etrnls 发表于 2011-5-2 00:09


O(n)的解法??感觉不对吧,感觉每次都会漏掉log(i)-2个sibling
回复

使用道具 举报

🔗
darksteel 2011-5-2 06:24:09 | 只看该作者
全局:
本帖最后由 darksteel 于 2011-5-2 06:26 编辑

回复 4# wwwyhx

3楼的思路应该是可以的,就是针对每个节点,链接左右儿子,或将左或右儿子与兄弟节点的儿子链接。这里需要假设当前层次及以上的节点已经全部处理好了,否则find_next无法正常工作。单个节点的逻辑有了,剩下的就是怎么与其它部分联系了,如果我们默认所有的兄弟指针都是从左往右指的话,那需要先递归右子树再递归左子树,以保证正确性。
代码片段:
  1. TREE_NODE *find_next(TREE_NODE *root)
  2. {
  3.         while(root = root->pSib) {
  4.                 if(root->pLft || root->pRgt)
  5.                         return root->pLft?root->pLft:root->pRgt;
  6.         }
  7.         return NULL;
  8. }
  9. void LinkLevelNodes(TREE_NODE *root)
  10. {
  11.         if(!root) return ;
  12.         if(root->pLft)
  13.                 root->pLft->pSib = root->pRgt?root->pRgt:find_next(root);
  14.         if(root->pRgt)
  15.                 root->pRgt->pSib = find_next(root);
  16.         LinkLevelNodes(root->pRgt);
  17.         LinkLevelNodes(root->pLft);
  18. }
复制代码


lz的结构定义命名太严谨,写起来十分艰难。
另外补充一句,算法复杂度是O(n)的。每个节点最多被访问常数次。欢迎指出bug。

评分

参与人数 1大米 +45 收起 理由
wwwyhx + 45

查看全部评分

回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-2 16:10:00 | 只看该作者
全局:
恩,是对的。这个是每次从上向下链接的,时间复杂度是O(n)
我想了一个从下回溯到顶层的,比它的复杂,时间复杂度也要高,
谢了。
回复

使用道具 举报

🔗
babyfrog 2011-6-25 06:41:44 | 只看该作者
全局:
本帖最后由 babyfrog 于 2011-6-26 00:36 编辑

用队列做算不算用了额外空间呢?

以下是直接可以run的代码:

  1. import java.util.LinkedList;

  2. public class SiblingNode {
  3.     public static void main(String[] args) {
  4.         Node n4 = new Node(4, null, null);
  5.         Node n5 = new Node(5, null, null);
  6.         Node n6 = new Node(6, null, null);
  7.         Node n7 = new Node(7, null, null);
  8.         Node n2 = new Node(2, n4, n5);
  9.         Node n3 = new Node(3, n6, n7);
  10.         Node root = new Node(1, n2, n3);
  11.         connectSiblingNodes(root);
  12.     }        
  13.         
  14.     static void connectSiblingNodes(Node root) {
  15.         LinkedList<Node> queue1 = new LinkedList<Node>();
  16.         LinkedList<Node> queue2 = new LinkedList<Node>();
  17.         queue1.add(root);
  18.         
  19.         while (!queue1.isEmpty()) {
  20.             //move the first node from queue1 to queue2
  21.             Node n = queue1.removeFirst(); queue2.add(n); Node last = n;
  22.             //print the node in the current level
  23.             System.out.print(n.value+" ");
  24.             //connect the siblings in the same level         
  25.             if (!queue1.isEmpty()) {
  26.                 System.out.print("->");
  27.                 last.next = queue1.getFirst(); last = last.next;
  28.                 continue;
  29.             }
  30.                
  31.             System.out.println();
  32.             while(!queue2.isEmpty()) {
  33.                 Node tmp = queue2.removeFirst();
  34.                 if (tmp.lchild != null) queue1.add(tmp.lchild);
  35.                 if (tmp.rchild != null) queue1.add(tmp.rchild);
  36.             }
  37.         }
  38.     }
  39. }

  40. class Node {
  41.     int value;
  42.     Node lchild;
  43.     Node rchild;
  44.     Node next;

  45.     Node(int v, Node l, Node r) {
  46.         this.value = v;
  47.         this.lchild = l;
  48.         this.rchild = r;
  49.     }
  50. }
复制代码


运行结果:
1
2->3
4->5->6->7
回复

使用道具 举报

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

本版积分规则

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