May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 804|回复: 5
收起左侧

狗面筋 电面 1个小题目没做好 :(

[复制链接] |试试Instant~ |关注本帖
dimi 发表于 2016-8-24 21:58:36 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Google - 内推 - 技术电面 |Other在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
给你一个多叉树。移出所有子树,当这个子树的全部节点的值的和为0。

我都写完了,但是中间出了几个bug. 代码也有点长,效果很不好。挂了。
谁试着写个elegent的解法把
. From 1point 3acres bbs

评分

1

查看全部评分

hxtang 发表于 2016-8-24 23:57:23 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
hxtang 发表于 2016-8-24 23:56
试着写了一个
后序遍历的思路是对的,但是要注意两点:
(1) 传TreeNode*的引用,这样即使要删root也能删
...

上面贴的代码不知道为啥抽风了...重新贴个
.1point3acres缃
struct TreeNode {
    vector<TreeNode*> children;. from: 1point3acres.com/bbs
    int val;
    TreeNode(int v) : val(v) {};
    ~TreeNode() { for (TreeNode* cnode: children) delete cnode; }
};

int subtree_sum(TreeNode* &pnode) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    if (pnode == nullptr) return 0;
.鏈枃鍘熷垱鑷1point3acres璁哄潧    int sum = pnode->val;-google 1point3acres
    for (TreeNode* cnode : pnode->children) sum += subtree_sum(cnode);.1point3acres缃
    if (sum == 0) {
        delete pnode;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        pnode = NULL;
    }
. more info on 1point3acres.com    return sum;
}
回复 支持 1 反对 0

使用道具 举报

dydcfg 发表于 2016-8-24 22:10:44 | 显示全部楼层
关注一亩三分地微博:
Warald
试着写了一下,后根序遍历,然后删子树并且返回当前子树的和.

int dfs(TreeNode* root){
        int ret=0;
        for (int i=0;i<(root->sons).size();i++){
                if (root->sons[i]!=NULL){. Waral 鍗氬鏈夋洿澶氭枃绔,
                        int subRet;
                        subRet=dfs(root->sons[i]);
                        if (subRet==0){
                                root->sons[i]=NULL;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        }. more info on 1point3acres.com
                        ret+=subRet;
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
        ret+=root->val;
        return ret;
}
回复 支持 反对

使用道具 举报

 楼主| dimi 发表于 2016-8-24 22:23:13 | 显示全部楼层
dydcfg 发表于 2016-8-24 22:10
试着写了一下,后根序遍历,然后删子树并且返回当前子树的和.

int dfs(TreeNode* root){
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
nice. your solution is very good... thanks.
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-8-24 22:45:01 | 显示全部楼层
谢谢楼主分享
好像这题在地里见过啊
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-8-24 23:56:17 | 显示全部楼层
试着写了一个
后序遍历的思路是对的,但是要注意两点:
(1) 传TreeNode*的引用,这样即使要删root也能删
(2) 如果一棵子树sum为0,需要迭代删掉整个子树
  1. struct TreeNode {
  2.     vector<TreeNode*> children;
  3.     int val;
  4.     TreeNode(int v) : val(v) {};. 1point3acres.com/bbs
  5.     ~TreeNode() { for (TreeNode* cnode: children) delete cnode; }
  6. };

  7. int subtree_sum(TreeNode* &pnode) {
  8.     if (pnode == nullptr) return 0;
  9.     int sum = pnode->val;
  10.     for (TreeNode* cnode : pnode->children) sum += subtree_sum(cnode);. visit 1point3acres.com for more.
  11.     if (sum == 0) {
  12.     <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">delete pnode;</span>
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-5-27 09:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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