一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 800|回复: 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
试着写了一个
后序遍历的思路是对的,但是要注意两点:. visit 1point3acres.com for more.
(1) 传TreeNode*的引用,这样即使要删root也能删
.1point3acres缃 ...

上面贴的代码不知道为啥抽风了...重新贴个
. from: 1point3acres.com/bbs
struct TreeNode {
    vector<TreeNode*> children;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    int val;
    TreeNode(int v) : val(v) {};. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    ~TreeNode() { for (TreeNode* cnode: children) delete cnode; }
};
.鏈枃鍘熷垱鑷1point3acres璁哄潧
int subtree_sum(TreeNode* &pnode) {
    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;
}
回复 支持 1 反对 0

使用道具 举报

dydcfg 发表于 2016-8-24 22:10:44 | 显示全部楼层
关注一亩三分地微博:
Warald
试着写了一下,后根序遍历,然后删子树并且返回当前子树的和.
. 鍥磋鎴戜滑@1point 3 acres
int dfs(TreeNode* root){
        int ret=0;
        for (int i=0;i<(root->sons).size();i++){
                if (root->sons[i]!=NULL){. from: 1point3acres.com/bbs
                        int subRet;
                        subRet=dfs(root->sons[i]);
                        if (subRet==0){
                                root->sons[i]=NULL;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        }
                        ret+=subRet;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                }
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
        ret+=root->val;. From 1point 3acres bbs
        return ret;
}
回复 支持 反对

使用道具 举报

 楼主| dimi 发表于 2016-8-24 22:23:13 | 显示全部楼层
dydcfg 发表于 2016-8-24 22:10. Waral 鍗氬鏈夋洿澶氭枃绔,
试着写了一下,后根序遍历,然后删子树并且返回当前子树的和.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
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也能删. 1point 3acres 璁哄潧
(2) 如果一棵子树sum为0,需要迭代删掉整个子树
  1. struct TreeNode {
  2.     vector<TreeNode*> children;
  3.     int val;
  4.     TreeNode(int v) : val(v) {};. more info on 1point3acres.com
  5.     ~TreeNode() { for (TreeNode* cnode: children) delete cnode; }
  6. };

  7. int subtree_sum(TreeNode* &pnode) {
  8.     if (pnode == nullptr) return 0;. 鍥磋鎴戜滑@1point 3 acres
  9.     int sum = pnode->val;. 鍥磋鎴戜滑@1point 3 acres
  10.     for (TreeNode* cnode : pnode->children) sum += subtree_sum(cnode);
  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>
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-26 09:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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