一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 643|回复: 5
收起左侧

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

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

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

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

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

x
给你一个多叉树。移出所有子树,当这个子树的全部节点的值的和为0。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我都写完了,但是中间出了几个bug. 代码也有点长,效果很不好。挂了。
谁试着写个elegent的解法把

评分

1

查看全部评分

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

int dfs(TreeNode* root){
        int ret=0;
        for (int i=0;i<(root->sons).size();i++){. Waral 鍗氬鏈夋洿澶氭枃绔,
                if (root->sons[i]!=NULL){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        int subRet;
                        subRet=dfs(root->sons[i]);
                        if (subRet==0){
                                root->sons[i]=NULL;
                        }
                        ret+=subRet;
                }
        }. from: 1point3acres.com/bbs
        ret+=root->val;
        return ret;
}
回复 支持 反对

使用道具 举报

 楼主| dimi 发表于 2016-8-24 22:23:13 | 显示全部楼层
dydcfg 发表于 2016-8-24 22:10
试着写了一下,后根序遍历,然后删子树并且返回当前子树的和.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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;. 1point3acres.com/bbs
  3.     int val;
  4.     TreeNode(int v) : val(v) {};
  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);
  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>
复制代码
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-8-24 23:57:23 | 显示全部楼层
hxtang 发表于 2016-8-24 23:56. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
试着写了一个
后序遍历的思路是对的,但是要注意两点:
(1) 传TreeNode*的引用,这样即使要删root也能删
...

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

struct TreeNode {
    vector<TreeNode*> children;
    int val;
    TreeNode(int v) : val(v) {};
    ~TreeNode() { for (TreeNode* cnode: children) delete cnode; }
};

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;
-google 1point3acres    }
    return sum;
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 23:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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