代码随想录一刷记录Day15——leetcode110.平衡二叉树 257. 二叉树的所有路径

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