C++算法练习-day35——404.左叶子之和

题目来源：. - 力扣（LeetCode）

题目思路分析

题目要求计算给定二叉树中所有左叶子节点的和。叶子节点是指没有子节点的节点。左叶子节点是指位于某个节点的左子树中的叶子节点。

解决这个问题的思路如下：

1. 定义叶子节点：首先，我们需要一个函数来判断一个节点是否是叶子节点。
2. 递归遍历：然后，我们使用递归的方法遍历整棵树。
3. 判断和累加：在遍历的过程中，我们检查当前节点的左子节点，如果它是叶子节点，则将其值累加到结果中；如果不是叶子节点，则递归地计算其左子树中所有左叶子节点的和。对于右子树，我们只需递归地计算其所有左叶子节点的和（因为当前节点的右子树与当前节点的左叶子节点无关）。

代码:

/**  
 * Definition for a binary tree node.  
 * struct TreeNode {  
 *     int val;  
 *     TreeNode *left;  
 *     TreeNode *right;  
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}  
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  
 * };  
 */  
class Solution {  
public:  
    // 判断一个节点是否是叶子节点  
    bool isLeaves(TreeNode* root){  
        // 叶子节点没有左子节点和右子节点  
        return (!root->left && !root->right);  
    }  
      
    // 计算二叉树中所有左叶子节点的和  
    int sumOfLeftLeaves(TreeNode* root) {  
        // 如果当前节点为空，返回0  
        if(!root) return 0;  
          
        int ans = 0;  
          
        // 检查左子节点  
        if(root->left){  
            // 如果左子节点是叶子节点，将其值累加到结果中  
            // 否则，递归地计算其左子树中所有左叶子节点的和  
            ans += isLeaves(root->left) ? root->left->val : sumOfLeftLeaves(root->left);  
        }  
          
        // 对于右子树，只需递归地计算其所有左叶子节点的和  
        // 注意：这里先检查root->right是否存在且不是叶子节点，以优化性能  
        if(root->right && !isLeaves(root->right)){  
            ans += sumOfLeftLeaves(root->right);  
        }  
          
        return ans;  
    }  
};

知识点摘要

1. 叶子节点的定义：没有左子节点和右子节点的节点被称为叶子节点。
2. 递归遍历：递归是一种解决树结构问题的常用方法，通过不断地将问题分解为子问题来解决。
3. 条件判断：在编程中，使用条件判断语句（如if语句）来根据条件执行不同的代码块。
4. 累加操作：使用累加器（如变量ans）来存储和计算一系列数值的总和。

通过本题，我们学习了如何判断一个节点是否是叶子节点，以及如何使用递归的方法遍历二叉树并计算特定节点的和。递归是一种强大的编程技巧，特别适用于解决树结构相关的问题。在实际应用中，我们还需要注意递归的深度，以避免出现栈溢出等问题。通过不断地练习和思考，我们可以更加熟练地掌握这种技巧，并将其应用于更复杂的场景中。

原文地址：https://blog.csdn.net/L613Z/article/details/142993671

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！