leetcode222.完全二叉树结点的数量
这个是使用后序遍历来写的，什么二叉树都可以，没用到完全二叉树的条件
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0; // 如果节点为空，返回 0
// 递归计算左子树和右子树的节点数
int leftCount = countNodes(root->left);
int rightCount = countNodes(root->right);
// 总节点数 = 左子树节点数 + 右子树节点数 + 当前节点(1)
return leftCount + rightCount + 1;
}
};
leetcode 110.平衡二叉树
给定一个二叉树，判断它是否是
平衡二叉树
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
我一开始自己写的代码，只部分通过了一些案例，因为递归终止条件的处理不够完善
问题：
当 leftlength 或 rightlength 为 -1（表示子树不平衡）时，你仍然尝试计算 abs(leftlength - rightlength)，这会导致错误。
修正：
在递归中，如果某个子树返回 -1，说明已经不平衡，直接返回 -1，避免继续计算.
/**
* 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 isBalanced(TreeNode* root) {
if(checkheight(root)!=-1)
return true;
else return false;
}
int checkheight(TreeNode* root){
if(root==nullptr) return 0;
int leftlength= checkheight(root->left);
int rightlength= checkheight(root->right);
if(abs(leftlength-rightlength)>1) return -1;
return max(leftlength,rightlength)+1;
}
};正确代码：
class Solution {
public:
bool isBalanced(TreeNode* root) {
return checkheight(root) != -1;
}
private:
int checkheight(TreeNode* root) {
if (root == nullptr) return 0;
// 检查左子树高度
int leftlength = checkheight(root->left);
if (leftlength == -1) return -1; // 左子树不平衡，提前返回
// 检查右子树高度
int rightlength = checkheight(root->right);
if (rightlength == -1) return -1; // 右子树不平衡，提前返回
// 判断当前节点是否平衡
if (abs(leftlength - rightlength) > 1) return -1;
// 返回当前节点高度
return max(leftlength, rightlength) + 1;
}
};
leetcode257.二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
回溯算法：
class Solution {
private:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中
// 这才到了叶子节点
if (cur->left == NULL && cur->right == NULL) {
string sPath;
for (int i = 0; i < path.size() - 1; i++) {
sPath += to_string(path[i]);
sPath += "->";
}
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;
}
};