代码随想录一刷记录Day15——leetcode110.平衡二叉树 257. 二叉树的所有路径
前言
之前就有刷代码随想录，但奈何总是三天打鱼两天晒网，而且刷的也很囫囵吞枣，于是乎决定参加代码随想录训练营，准备精刷一遍，希望自己能坚持下去，结营后自己的算法水平能更上一个level，冲ing！
leetcode110.平衡二叉树
题目链接leetcode110.平衡二叉树
思路
判断一棵树是否是平衡二叉树——>主要看每个节点 的左右两个子树的高度差的绝对值是否超过1
所以要求树高度，那么就要用到后序遍历（左右根），因为这样才能逐步向下，即依次获得左的高度、右的高度，然后才能得到根的高度：左右取大+1。
本题具体采用递归的方法进行遍历，递归三要素：
1、递归参数和返回值
参数是当前传入的节点；返回值是以当期节点为根节点的高度
2、终止条件
递归的过程中遇到空节点就终止，返回0，表示当前节点为根节点的树高度为0
3、单层递归逻辑
求该节点左子树高度，求该节点右子树高度，求该节点高度（左右大的那个+1），如果左右节点高度差值>1就返回-1，说明不平衡
代码
classSolution{public://返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树则返回-1intgetHeigh(TreeNode*node){if(node==nullptr){return0;}intleftHeigh=getHeigh(node->left);if(leftHeigh==-1)return-1;intrightHeigh=getHeigh(node->right);if(rightHeigh==-1)return-1;returnabs(leftHeigh-rightHeigh)>1?-1:1+max(leftHeigh,rightHeigh);}boolisBalanced(TreeNode*root){returngetHeigh(root)==-1?false:true;}};leetcode257. 二叉树的所有路径
题目链接leetcode257. 二叉树的所有路径
思路
本题要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
当走到叶子节点后，即左右子树都为空，此时该回溯，回到上一节点继续搜索其他可能的路径。
因为回溯其实也是递归，所以本题依然参照递归的方式进行前序遍历。
代码
classSolution{private:voidtraversal(TreeNode*cur,vector<int>&path,vector<string>&result){path.push_back(cur->val);if(cur->left==NULL&&cur->right==NULL){string sPath;for(inti=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)returnresult;traversal(root,path,result);returnresult;}};leetcode404.左叶子之和
题目链接leetcode404.左叶子之和
思路
本题求的是所有左叶子之和，那么首先要清楚如何判断一个节点是否是左叶子。值得注意的是本题不像之前的二叉树题，本题仅通过判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子，因此不能一步到位直接遍历到最终。具体判断方式为如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。判断代码为：
if(node->left!=NULL&&node->left->left==NULL&&node->left->right==NULL){左叶子节点处理逻辑}遍历方式依然采用递归遍历（后序），因为每个节点的左叶子和都要向上传递给父亲，所以是左右中，即后序遍历
代码
classSolution{public:intsumOfLeftLeaves(TreeNode*root){if(root==NULL)return0;if(root->left==NULL&&root->right==NULL)return0;intleftValue=sumOfLeftLeaves(root->left);// 左if(root->left&&!root->left->left&&!root->left->right){// 左子树就是一个左叶子的情况leftValue=root->left->val;}intrightValue=sumOfLeftLeaves(root->right);// 右intsum=leftValue+rightValue;// 中returnsum;}};leetcode222.完全二叉树的节点个数
题目链接leetcode222.完全二叉树的节点个数
思路
方法一：普通二叉树求法
按照普通二叉树来求的话，这道题目的递归法和求二叉树的深度写法类似。递归遍历的顺序依然是后序（左右中）。
**首先确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
然后确定终止条件：如果为空节点的话，就返回0，表示节点数为0。
最后确定单层递归的逻辑：**先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
方法二：完全二叉树求法
因为题目告诉了给的是一颗完全二叉树，故可以利用其一些性质来求。
一个完全二叉树，若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，不过需要注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
代码
// 方法一classSolution{private:intgetNodesNum(TreeNode*cur){if(cur==NULL)return0;intleftNum=getNodesNum(cur->left);// 左intrightNum=getNodesNum(cur->right);// 右inttreeNum=leftNum+rightNum+1;// 中returntreeNum;}public:intcountNodes(TreeNode*root){returngetNodesNum(root);}};//方法二classSolution{public:intcountNodes(TreeNode*root){if(root==nullptr)return0;TreeNode*left=root->left;TreeNode*right=root->right;intleftDepth=0,rightDepth=0;// 这里初始为0是有目的的，为了下面求指数方便while(left){// 求左子树深度left=left->left;leftDepth++;}while(right){// 求右子树深度right=right->right;rightDepth++;}if(leftDepth==rightDepth){return(2<<leftDepth)-1;// 注意(2<<1) 相当于2^2，所以leftDepth初始为0}returncountNodes(root->left)+countNodes(root->right)+1;}};