代码随想录算法训练营第十五天|110平衡二叉树、257二叉树的所有路径 、404左叶子之和、222完全二叉树的节点个数

day15

1. 110平衡二叉树

递归三步分析

(1)明确递归函数的参数和返回值

• 参数：当前节点 node，代表以此节点为根的子树。
• 返回值：若当前节点为根的子树是平衡的，返回该子树的高度；若不平衡，返回 -1 作为标记。

这样设计的原因是，一旦子树不平衡，后续的递归也没有必要继续判断，因此返回 -1 来直接传递不平衡的信息。

(2)明确递归的终止条件

• 递归遇到空节点时终止，返回高度 0，因为空节点的高度定义为 0，且为空节点时自然符合平衡条件。

if (node == NULL) {return 0;
}

(3)明确单层递归的逻辑

• 要判断当前节点为根的子树是否平衡，关键在于左右子树高度差的绝对值是否超过 1。

  • 首先递归计算当前节点的左子树高度 leftHeight。如果 leftHeight 为 -1，表示左子树不平衡，直接返回 -1。

  • 其次递归计算右子树高度 rightHeight。如果 rightHeight 为 -1，表示右子树不平衡，直接返回 -1。

  • 如果左右子树的高度差绝对值大于 1，也返回 -1 表示当前子树不平衡。

  • 否则，返回以当前节点为根的子树的高度，即 1 + max(leftHeight, rightHeight)。

整体代码如下：

class Solution {
public:// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1int getHeight(TreeNode* node) {if (node == NULL) {return 0;}int leftHeight = getHeight(node->left);if (leftHeight == -1) return -1;int rightHeight = getHeight(node->right);if (rightHeight == -1) return -1;return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);}bool isBalanced(TreeNode* root) {return getHeight(root) == -1 ? false : true;}
};

2. 257二叉树的所有路径

通过递归遍历二叉树，记录从根节点到叶子节点的路径。每次找到一条路径时，将其转换为字符串并加入结果集中。关键在于回溯的思想，它确保路径的正确性，避免混入多余节点。以下是代码的详细解析：

三步理解递归逻辑

(1) 明确递归函数的参数和返回值

• 参数:
  • TreeNode* cur：当前递归处理的节点。
  • vector<int>& path：用于记录从根节点到当前节点的路径。
  • vector<string>& result：存放最终的所有路径结果。
• 返回值：递归函数 traversal 不需要返回值，因为所有的路径会直接存入 result。

代码实现：

void traversal(TreeNode* cur, vector<int>& path, vector<string>& result);

(2) 明确递归终止条件

• 终止条件是当前节点 cur 为叶子节点（即左右子节点都为空）。
• 当到达叶子节点时，将 path 中的路径转为字符串并加入 result。

注：这里不需要判断 cur 是否为空，因为在递归中已经确保了传入的节点不会是空节点。

if (cur->left == NULL && cur->right == NULL) { // 叶子节点string sPath;for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]) + "->"; // 将路径转换为字符串格式}sPath += to_string(path[path.size() - 1]); // 加入最后一个节点值result.push_back(sPath); // 收集当前路径return;
}

(3) 明确单层递归逻辑

在递归的每一层中，我们：

• 记录路径：首先将当前节点的值加入到 path，表示路径更新。

• 递归遍历左右子树：

​ - 先判断左子树是否存在，如果存在就递归调用。

​ - 每次递归返回后，立即执行回溯操作，将当前节点从 path 中移除，以便路径状态恢复，准备进入右子树。

• 回溯：回溯的作用是在每次递归结束后，将路径状态恢复到递归前的状态。这是通过 path.pop_back() 实现的。确保左、右子树分别递归时路径不混淆。

path.push_back(cur->val); // 当前节点值加入路径
if (cur->left) { // 递归左子树traversal(cur->left, path, result);path.pop_back(); // 回溯，移除当前节点值
}
if (cur->right) { // 递归右子树traversal(cur->right, path, result);path.pop_back(); // 回溯
}

完整代码

class Solution {
private:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {path.push_back(cur->val); // 当前节点加入路径if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点string sPath;for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]) + "->";}sPath += to_string(path[path.size() - 1]); // 加入叶子节点result.push_back(sPath); // 收集路径return;}if (cur->left) {traversal(cur->left, path, result); // 递归左子树path.pop_back(); // 回溯}if (cur->right) {traversal(cur->right, path, result); // 递归右子树path.pop_back(); // 回溯}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result; // 空树情况traversal(root, path, result);return result;}
};

回溯指的是在递归过程中，将路径恢复到前一个状态。每次递归后我们会“回退”上一个节点，保持路径与当前递归状态一致。这种机制保证在遍历不同子树时路径不会交叉或干扰。

3. 404左叶子之和

明确每层递归的目标：我们希望每一层递归能够返回以当前节点为根的树中所有左叶子节点的值之和。

考虑终止条件：在递归中，终止条件指的是在什么情况下可以直接返回结果，而不需要继续递归。

• 空节点：当节点为 NULL 时，我们直接返回 0，因为空节点没有左叶子节点。
• 叶子节点：如果当前节点是叶子节点（没有左右孩子），也返回 0，因为我们要找的是“左叶子节点”。

单层递归逻辑：

• 首先递归求左子树的左叶子节点之和。
• 如果当前节点的左子节点是左叶子节点（即没有子节点），就直接把它的值加到结果中。
• 接着递归求右子树的左叶子节点之和，右子树中不会存在从当前节点直接得到的左叶子节点。只有在当前节点的左子树里，我们才可能找到“左叶子节点”；右子树中的节点即使是叶子节点，也不符合“当前节点的左叶子节点”的条件。

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right== NULL) return 0;int leftValue = sumOfLeftLeaves(root->left);    // 左if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况leftValue = root->left->val;}int rightValue = sumOfLeftLeaves(root->right);  // 右int sum = leftValue + rightValue;               // 中return sum;}
};

4. 222完全二叉树的节点个数

递归终止条件：

• if(root == NULL) return 0;
  这里的判断处理了空节点的情况，即如果当前节点为空，返回0，因为空节点不算入节点总数。

递归计算左、右子树的节点数：

• int l = countNodes(root->left);
  递归调用 countNodes 函数计算左子树的节点总数，并将结果存储在 l 中。
• int r = countNodes(root->right);
  递归调用 countNodes 函数计算右子树的节点总数，并将结果存储在 r 中。

合并结果：

• int sum = 1 + l + r;
  这里计算当前节点为根的子树总节点数。1 表示当前节点，l 和 r 分别表示左子树和右子树的节点数量。
• return sum;
  返回当前子树的节点总数。

class Solution {
public:int countNodes(TreeNode* root) {if(root==NULL) return 0;int l=countNodes(root->left);int r=countNodes(root->right);int sum=1+l+r;return sum;}
};