小赖子的英国生活和资讯

C++ 编程练习题: 左子树叶节点之和 (深度优先搜索+广度优先搜索+递归算法)

JustYY.com 小赖子的英国生活和资讯
阅读 桌面完整版
learn-to-code C++ 编程练习题: 左子树叶节点之和 (深度优先搜索+广度优先搜索+递归算法) ACM题解 C++ C++ 学习笔记 数据结构与算法 程序设计 计算机

学编程

题意: 找出所有左子树上的叶节点的值之和. 

   3
   / \
  9  20
    /  \
   15   7

比如上面 9 和15是左子树上的子节点, 那么求和得 24.

一般来说, 遍历树有两种方式: 深度优先DFS和广度优先BFS. 解这题的关键就在需要知道叶子节点是从左边来的还是从右边来的.

C++ 定义二叉树

1
2
3
4
5
6

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

广度优先 BFS (Breadth First Search)

我们需要用一个队列来实现广度优先. 每次循环的时候从队首取出一个节点, 然后把它的子节点(也就是左右子节点, 如果有的话)添加到队列中, 直到队列为空. 我们还需要把左右子节点的状态(也就是左边还是右边)记录到节点中, 所以我们用了一个 std::pair 这么一个数据结构. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        queue< pair<TreeNode*, bool> > q;
        q.push(make_pair(root, false));
        auto r = 0;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first->left == NULL && p.first->right == NULL && p.second) {
                r += p.first->val;  // sum the value if it comes from left
            }
            if (p.first->left) {
                q.push(make_pair(p.first->left, true));                
            }
            if (p.first->right) {
                q.push(make_pair(p.first->right, false));
            }
        }
        return r;        
    }
};
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        queue< pair<TreeNode*, bool> > q;
        q.push(make_pair(root, false));
        auto r = 0;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first->left == NULL && p.first->right == NULL && p.second) {
                r += p.first->val;  // sum the value if it comes from left
            }
            if (p.first->left) {
                q.push(make_pair(p.first->left, true));                
            }
            if (p.first->right) {
                q.push(make_pair(p.first->right, false));
            }
        }
        return r;        
    }
};

BFS访问树是一层一层访问的.

深度优先 DFS (Depth First Search)

深度优先访问树的方式也很直观, 就是一条路能往左下走就往左下走, 直到叶子节点, 然后再回溯到右节点. 我们可以通过递归的方式 来实现, 当然也可以自己创建和维护堆栈来实现DFS. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    void walk(TreeNode* root, bool left) {
        if (root == NULL) return;
        // leaf
        if (root->left == NULL && root->right == NULL) {
            if (left) { // sum only left branches
                sum += root->val;
            }
        }
        if (root->left != NULL) { // DFS left sub tree
            walk(root->left, true);
        }
        if (root->right != NULL) { // DFS right sub tree
            walk(root->right, false);
        }
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (root) {
            walk(root->left, true);
            walk(root->right, false);
        }
        return sum;
    }
private:
    int sum = 0;
};
class Solution {
public:
    void walk(TreeNode* root, bool left) {
        if (root == NULL) return;
        // leaf
        if (root->left == NULL && root->right == NULL) {
            if (left) { // sum only left branches
                sum += root->val;
            }
        }
        if (root->left != NULL) { // DFS left sub tree
            walk(root->left, true);
        }
        if (root->right != NULL) { // DFS right sub tree
            walk(root->right, false);
        }
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (root) {
            walk(root->left, true);
            walk(root->right, false);
        }
        return sum;
    }
private:
    int sum = 0;
};

如果是递归的话, 当这棵树的深度过大, 就很有可能会堆栈溢出(因为堆栈的大小是有限的).

英文: C++ Coding Exercise – Sum of Left Leaves (BFS + DFS + Recursion)

C/C++编程

强烈推荐

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

相关文章：

  1. Javascript 中 sleep 函数实现 阅读 桌面完整版 Javascript 中并没有 built-in 的 sleep 函数支持, 在 async/await/Promise 的支持之前, 我们可以用 busy-waiting 的方式来模拟: 1...
  2. C++ 编程练习题: 如何合并两个二叉树? 阅读 桌面完整版 题意: 合并两个二叉树, 没有说不可以改变原来的二叉树. 合并的时候把结点求合. C/C++ 中二叉树的定义 在C或者C++中, 二叉树的定义可以很方便的用结构体来表征. 其中左右子树都是递归定义. 1 2 3 4...
  3. 被动收入之: 微博红包 阅读 桌面完整版 今年开始重新经营我的微博帐号 drlai 收到两笔微信红包，应该是来自于官方的支持，150元（成功提现到支付宝）。虽然这不能持久，也没多少，但毕竟实现了零的突破，意义重大。 如果流量上来，内容创作者可能会接受到比较多的赞赏，这也是一个比较简单的变现方法。这也能作为一种被动收入，不过如果不是头部网红，可能杯水车薪，但如果你有好几个类似这样的，也能积少成多！ 在用户中心，微博用户可以每天登陆手机微博APP打卡，获取点数和少量的红包钱（几分钱），积少成多！ 微博做些小任务可获得积分和几分钱。聊胜于无。 微博的主要盈利模式 微博的主要盈利模式主要包括以下几个方面： 广告收入：微博的大部分收入来源于广告，尤其是品牌广告和效果广告。广告形式包括信息流广告（类似于推文广告）、热门话题广告、开屏广告和视频广告。品牌和企业可以利用微博庞大的用户群和社交互动来提升曝光率、推广品牌和产品。 会员服务：微博提供的VIP会员服务，用户可以支付订阅费用来享受更多的特权，比如个性化的主题、特有的表情包、私密权限设置等。这些会员服务主要面向个人用户，提升其社交体验。 直播和打赏：微博提供直播平台，用户可以通过购买虚拟礼物来支持主播，微博会从这些打赏中抽取一定比例的分成。此外，微博与内容创作者分成，通过内容付费、知识付费等形式变现。 增值服务：针对企业和大V（拥有大量粉丝的用户），微博还提供增值服务，如账号认证、粉丝数据分析、精准推送、推广和营销工具等。这些服务帮助企业提升营销效果，同时也增加了微博的收入来源。 电商和导流：微博上有大量的电商导流业务，尤其是和明星、网红的合作推广。微博用户在浏览社交内容时，可以直接跳转到商品购买链接，微博通过这种方式赚取导流佣金。...
  4. 入佳能 6D Mark II 入门级全幅单反 阅读 桌面完整版 一直以来都想要全幅的单反, 在之前入了经典24-70mm F2.8佳能红圈镜头 (万能焦), 但是一直机身还是半画幅的 T3i, 朋友就说这红圈镜头需要在全幅单反上才能发挥最大的功效. 考虑许久, 咬咬牙, 入了佳能 6D Mark II...
  5. 你给SteemIt中文微信群拖后腿了么? 阅读 桌面完整版 这年头不缺算法, 就缺数据. 这两天花了很多时间在整API上, 整完之后自己用了一下还觉得真是挺方便的. 今天就突然想看一看自己是否给大家拖后腿了, 于是调用每日中文区微信群排行榜单的API, 刷刷拿着 NodeJs 练手: 1 2 3 4...
  6. 换了个奥迪Q5大灯花了我1000英镑 阅读 桌面完整版 我那辆奥迪Q5 SUV今年年检没通过，原因是左前车灯坏了，需要更换。车厂告诉我，光是订购零件就要700多英镑，加上人工费，总费用得1000英镑。但没办法，如果不修，车辆年检（MOT）就过不了，车也不能上路。 MOT是英国的机动车强制性安全检测（Ministry of Transport Test）的简称。 近侧前位置灯不工作 drl/位置灯集成（4.2.1(a)(ii)） Nearside Front Position lamp not...
  7. 网站升级 阅读 桌面完整版 前段时间手欠, 服务器提供了免费的 升级,点了就发现文件在转移的时候没有拷贝完全,导致了网站一个星期不能使用. 后来升级了SSL空间,以前的博客地址就不能用了, 不过不要紧,还是用 justyy.com 访问即可. 强烈推荐 英国代购-畅购英伦 TopCashBack 返现 (英国购物必备, 积少成多,...
  8. 《Steem 指南》之 justyy 在线工具与 API 系列 – 同时给多个帐号发送SBD或者STEEM 阅读 桌面完整版 同时给多个帐号发送SBD或者STEEM STEEMIT 和 BUSY 的前端都有一个内置的钱包工具, 您可以一次给一个帐号发送 SBD 或者 STEEM. 当我们要给很多很多人发送钱的时候, 就显得有些不方便了. 这时候可以用这个在线工具: https://steemyy.com/wallet-tool/...
Exit mobile version