完全二叉树的节点个数

方法一：可以用递归法遍历一遍左子树和右子树的个数之和再加1等于全部节点个数

class Solution {
public:int getcount(TreeNode* cur){if(cur==NULL) return 0;int leftcount = getcount(cur->left);int rightcount = getcount(cur->right);return leftcount + rightcount + 1;}int countNodes(TreeNode* root) {return getcount(root);}
};
//写法2：
class Solution {
public:int countNodes(TreeNode* root) {if(root==NULL) return 0;int leftCount = countNodes(root->left);int rightCount = countNodes(root->right);return leftCount + rightCount + 1;}
};

方法二：用层序遍历方式遍历一遍所有节点

class Solution {
public:int countNodes(TreeNode* root) {queue<TreeNode*>que;if(root==NULL) return 0;que.push(root);int count = 0;while(!que.empty()){int size = que.size();for(int i=0; i<size; i++){TreeNode* node = que.front();que.pop();count++;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return count;}
};

平衡二叉树

判断左子树和右子树是不是高度相差1，用-1来表示不是平衡二叉树
用递归遍历的方式来解决

class Solution {
public:int getHeight(TreeNode* cur){if(cur==NULL) return 0;int leftHeight = getHeight(cur->left);if(leftHeight==-1) return -1;int rightHeight = getHeight(cur->right);if(rightHeight==-1) return -1;return abs(leftHeight-rightHeight) > 1 ? -1 : max(leftHeight,rightHeight)+1;}bool isBalanced(TreeNode* root) {return getHeight(root) == -1 ? false : true;}
};

我可以去掉max(leftHeight,rightHeight)吗？？？
在当前代码逻辑中，max(leftHeight, rightHeight) + 1 这部分是必须的，不能去掉。这是因为：

计算树的高度：max(leftHeight, rightHeight) + 1 的目的是计算当前节点的高度。这是标准的递归方式，左右子树的高度最大值加1，代表了当前节点的高度。如果去掉这部分，函数将无法正确计算树的高度，这会影响到是否平衡的判断。递归的基础：在递归过程中，每个节点的高度依赖于它的左右子树的高度。max(leftHeight, rightHeight) + 1 确保了递归向上传播时，每层都能正确反映子树的高度，从而可以正确判断平衡性。平衡判断依赖高度：代码依赖高度差来判断平衡性。虽然直接的平衡判断是通过 abs(leftHeight - rightHeight) > 1 来实现的，但整体高度的递归更新依赖 max(leftHeight, rightHeight) + 1。如果去掉这部分，无法准确获取节点的高度差，从而影响对平衡性的判断。

总结来说，max(leftHeight, rightHeight) + 1 是递归计算高度和判断平衡性的一部分，去掉它会导致无法正确计算节点高度，也就无法正确判断树是否平衡。因此，这部分代码是必须保留的。

二叉树的所有路径

左叶子之和

1. 递归方法
   通过叶子节点的父节点来访问叶子节点

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);return leftValue + rightValue;}
};

2. 层序遍历
   依然是遍历每一个节点，并用父节点来判断左节点是否为叶子节点

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {queue<TreeNode*>que;if(root==NULL) return 0;que.push(root);int sum = 0;while(!que.empty()){int size = que.size();while(size--){TreeNode* node = que.front();que.pop();if(node->left && !node->left->left && !node->left->right){sum+=node->left->val;}if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return sum;}
};