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

学编程

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

   3
   / \
  9  20
    /  \
   15   7

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

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

C++ 定义二叉树

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

广度优先 BFS (Breadth First Search)

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

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.

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++编程

• 理解C++中的std::transform_reduce及示例
• 使用原子 TAS 指令实现自旋锁
• C++中检测编译时与运行时: if consteval 与 std::is_constant_evaluated()
• C++ 转发引用: 完美转发的关键
• 理解 C++ 中的 dynamic_cast: 安全的向下转型与向上转型
• C与C++: restrict关键字及其在编译器优化中的作用
• C++的左值/lvalue, 右值/rvalue和右值引用/rvalue references
• C++中的assert和static_assert的区别
• C++: auto_ptr智能指针被弃用
• C++中的consteval是什么? 它与const和constexpr有何不同?
• C++ 教程: 用std::move来移动所有权
• C++中的 const和constexpr 比较
• 简易教程: C++的智能指针
• C++ 编程练习题: 如何合并两个二叉树?
• C++ 编程练习题 - 找出第三大的数
• C++ 编程练习题 - 最多连续的 1
• C++ 编程练习题 - 左子树叶节点之和 (深度优先+广度优先+递归)
• C++ 编程练习题 - 最多水容器 (递归)
• C++的异步编程: std::future, std::async 和 std::promise
• C编程练习题: 翻转整数位
• C++编程练习题: 找出字符串的所有大小小组合
• C/C++ 中的内存管理器(堆与栈)
• C++编程练习题: 对两单向链表求和