一亩三分地论坛

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

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

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

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

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

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

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

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

我都写完了,但是中间出了几个bug. 代码也有点长,效果很不好。挂了。.鏈枃鍘熷垱鑷1point3acres璁哄潧
谁试着写个elegent的解法把

评分

1

查看全部评分

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

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

struct TreeNode {
    vector<TreeNode*> children;. 1point3acres.com/bbs
    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;
    }
    return sum;. from: 1point3acres.com/bbs
}
回复 支持 1 反对 0

使用道具 举报

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

int dfs(TreeNode* root){
        int ret=0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        for (int i=0;i<(root->sons).size();i++){
                if (root->sons[i]!=NULL){
. 1point 3acres 璁哄潧                        int subRet;
                        subRet=dfs(root->sons[i]);
                        if (subRet==0){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                root->sons[i]=NULL;
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        ret+=subRet;
                }. visit 1point3acres.com for more.
        }
        ret+=root->val;. 1point3acres.com/bbs
        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 {-google 1point3acres
  2.     vector<TreeNode*> children;
  3.     int val;
  4.     TreeNode(int v) : val(v) {};
  5.     ~TreeNode() { for (TreeNode* cnode: children) delete cnode; }
  6. };

  7. int subtree_sum(TreeNode* &pnode) {. 1point3acres.com/bbs
  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) {
    . from: 1point3acres.com/bbs
  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-1-22 18:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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