代码随想录算法训练营第十五天|LeetCode 110 平衡二叉树、LeetCode 257 二叉树的所有路径、LeetCode 404 左叶子之和、LeetCode 222 完全二叉树的节点个数

参考文章均来自代码随想录 题目截图均来自力扣官网LeetCode 110 平衡二叉树参考文章链接平衡二叉树是左右一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。依旧是和高度有关 注意关于高度的递归就可以classSolution{public:// 返回以该节点为根节点的二叉树的高度如果不是平衡二叉树了则返回-1intgetHeight(TreeNode*node){if(nodeNULL){return0;}intleftHeightgetHeight(node-left);if(leftHeight-1)return-1;intrightHeightgetHeight(node-right);if(rightHeight-1)return-1;returnabs(leftHeight-rightHeight)1?-1:1max(leftHeight,rightHeight);}boolisBalanced(TreeNode*root){returngetHeight(root)-1?false:true;}};LeetCode 257 二叉树的所有路径参考文章链接本题涉及到回溯问题 回溯和递归是一一对应的有一个递归就要有一个回溯后面回溯板块应该会深入学一下 下面引入、用代码随想录代码 后面要重看看这道题classSolution{private:voidtraversal(TreeNode*cur,vectorintpath,vectorstringresult){path.push_back(cur-val);// 中中为什么写在这里因为最后一个节点也要加入到path中// 这才到了叶子节点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;}};LeetCode 404 左叶子之和参考文章链接首先要注意是判断左叶子不是二叉树左侧节点所以不要上来想着层序遍历。判断当前节点是不是左叶子是无法判断的必须要通过节点的父节点来判断其左孩子是不是左叶子。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;}};LeetCode 222 完全二叉树的节点个数参考文章链接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;}};