代码随想录第十九天 | 110.平衡二叉树，257. 二叉树的所有路径，404.左叶子之和，222. 完全二叉树的节点个数

110. 平衡二叉树

第一想法：首先要明确平衡二叉树的定义？左右节点的高度差不超过1？不会概念感觉无法下手...

返回参数返回int,为了标记已经不是平衡二叉树，用-1作标记

int traversal(TreeNode* root){if(root==nullptr) return 0;//递归左孩子和右孩子int leftdepth = traversal(root->left);int rightdepth = traversal(root->right);//如果左右孩子有-1，直接返回-1if (leftdepth==-1) return -1;if(rightdepth==-1) return -1;int result = abs(leftdepth-rightdepth) > 1? -1:max(leftdepth, rightdepth)+1;//判断左右孩子是否为-1return result;}bool isBalanced(TreeNode* root) {if(root==nullptr) return true;int result = traversal(root);if(result == -1) return false;else return true;}

看完想法：概念差不多正确，完整的高度平衡的二叉树定义是：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1，迭代记录节点当前的高度，如果不是平衡二叉树的话，就记为-1

257. 二叉树的所有路径

第一想法：和普通递归一样，在push_back根节点以及左右孩子的If都不执行的时候，开始把string转化为result

看完想法：一般的递归是 root==nullptr 的时候处理递归逻辑，但是与题目不符，我们需要遇到叶子节点的时候就放入result。并且遍历的时候用path遍历，类型是vector<int>, str作为result的元素，是一个暂存元素的中间变量。其中，把其他元素转变为string可以用to_string( )库函数。在执行递归回溯时，str的弹出（vector）可以用pop_back();

终止逻辑如下：

if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点string sPath;for (int i = 0; i < path.size() - 1; i++) { // 将path里记录的路径转为string格式sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]); // 记录最后一个节点（叶子节点）result.push_back(sPath); // 收集一个路径return;
}

完整版

void traversal(TreeNode* root, vector<int>& str, vector<string>& result){//中，提前放入strstr.push_back(root->val);if(root->left == nullptr && root->right == nullptr) {//终止条件string path;for(int i = 0; i<str.size()-1; i++){path += to_string(str[i]); path += "->";}path += to_string(str[str.size()-1]);result.push_back(path);}//递归规则if(root->left) {traversal(root->left, str, result);str.pop_back();}if(root->right) {traversal(root->right, str, result);str.pop_back();}}  vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> str;if(root==nullptr) return result;traversal(root, str, result);return result; 

第一想法：重点判断是不是左叶子，需要通过父节点来判断是不是左叶子。具体来说，当前遍历节点的左节点没有孩子并右节点有孩子，就是左叶子

看完想法：忽略了一点，最后需要求左子树的左叶子之和和右子树的左叶子之和才行，因此递归函数返回值应该是Int,，判断是不是叶子节点需要放在递归逻辑模块里

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

第一想法：用最大深度的解法去解完全ok，但是达不到理想的时间复杂度。不知道咋利用完全二叉树的个性

看完想法：完全二叉树：除了底层节点没满，其余节点都满了，并且底层节点都集中在树的左侧，节点不连续排列不是完全二叉树！

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。怎么判断是否为满二叉树，看左侧深度和右侧深度是否相同，同就是满二叉树；并且没有遍历中间节点，在二叉树很大的时候节约了很多时间成本.

在写终止条件时，要判断是否先等，不同则继续迭代；写递归逻辑时仍然要返回result

int result = 0;int traversal(TreeNode* root){if(root==nullptr) return 0;int leftdepth=0;int rightdepth=0;//记录左右侧深度，从0开始TreeNode* left = root->left;TreeNode* right = root->right;while(left){left = left->left;leftdepth++;}while(right){right = right->right;rightdepth++;}if(leftdepth==rightdepth){return (2<<leftdepth)-1;}//遍历逻辑int leftnode = traversal(root->left);int rightnode = traversal(root->right);result = leftnode + rightnode +1; return result;}int countNodes(TreeNode* root) {if(root==nullptr) return 0;result = traversal(root);return result;}