一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

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

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

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

评分

1

查看全部评分

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

上面贴的代码不知道为啥抽风了...重新贴个

struct TreeNode {
    vector<TreeNode*> children;
    int val;
    TreeNode(int v) : val(v) {};
    ~TreeNode() { for (TreeNode* cnode: children) delete cnode; }
};. more info on 1point3acres.com
. visit 1point3acres.com for more.
int subtree_sum(TreeNode* &pnode) {. From 1point 3acres bbs
    if (pnode == nullptr) return 0;
    int sum = pnode->val;
    for (TreeNode* cnode : pnode->children) sum += subtree_sum(cnode);
    if (sum == 0) {
        delete pnode;
        pnode = NULL;
    }
    return sum;. From 1point 3acres bbs
}
回复 支持 1 反对 0

使用道具 举报

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

int dfs(TreeNode* root){. visit 1point3acres.com for more.
        int ret=0;
.鐣欏璁哄潧-涓浜-涓夊垎鍦        for (int i=0;i<(root->sons).size();i++){. 1point 3acres 璁哄潧
                if (root->sons[i]!=NULL){
                        int subRet;
                        subRet=dfs(root->sons[i]);. Waral 鍗氬鏈夋洿澶氭枃绔,
                        if (subRet==0){
                                root->sons[i]=NULL;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴                        }
                        ret+=subRet;
                }. 1point3acres.com/bbs
        }
        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 | 显示全部楼层
谢谢楼主分享
好像这题在地里见过啊
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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) {};
  5.     ~TreeNode() { for (TreeNode* cnode: children) delete cnode; }. 1point 3acres 璁哄潧
  6. };
  7. .1point3acres缃
  8. int subtree_sum(TreeNode* &pnode) {. 鍥磋鎴戜滑@1point 3 acres
  9.     if (pnode == nullptr) return 0;
  10.     int sum = pnode->val;
  11.     for (TreeNode* cnode : pnode->children) sum += subtree_sum(cnode);
  12.     if (sum == 0) {. 1point 3acres 璁哄潧
  13.     <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">delete pnode;</span>
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2017-2-21 23:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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