算法训练营day13||110.平衡二叉树 257.二叉树的所有路径 404.左叶子之和 222.完全二叉树的节点个数

110.平衡二叉树第一想法最大深度最小深度判断是不是1看完视频后比较高度必然用后续遍历递归三部曲1.确定函数的传入参数和返回值传入当前节点返回以当前传入节点为根节点的树的高度如果左右子数的差值已经大于1了直接返回12.明确中止条件当当前节点为空时表示以当前节点为根节点的树的高度为03.确认单层递归逻辑后序遍历/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int gethight(TreeNode* node) { if(nodeNULL) return 0; int lefthightgethight(node-left); if(lefthight-1) return -1; int righthightgethight(node-right); if(righthight-1) return -1; int res; if(abs(lefthight-righthight)1) return -1; else { res1max(lefthight,righthight); return res; } } bool isBalanced(TreeNode* root) { return gethight(root)-1? false:true; } };257.二叉树的所有路径第一想法和求深度好像有点像后续遍历看完题解因为要从根节点到叶子节点所以使用前序遍历这样才方便让父节点指向孩子节点递归三部曲1.确定函数的传入值参数和返回值传入根节点记录每一条路径的path和存放结果集的result不需要返回值2.确定终止条件当找到了叶子节点时表示终止也就是当它的左右孩子都为空时if(cur-leftNULLcur-rightNULL) { 终止处理逻辑 }再来写终止处理逻辑使用vectoeint结构来记录path所以要把vectorint结构的path转为 string格式再把这个string放进result里这里使用vectorInt的原因是使用vector方便做回溯3.确定单层递归逻辑前序遍历先处理中间节点中间节点就是我们要记录路径上的节点先放入path中然后是递归和回溯if (cur-left) { traversal(cur-left, path, result); path.pop_back(); // 回溯 } if (cur-right) { traversal(cur-right, path, result); path.pop_back(); // 回溯 }整体代码如下/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ // 版本一 class Solution { private: void traversal(TreeNode* cur, vectorint path, vectorstring result) { path.push_back(cur-val); // 中中为什么写在这里因为最后一个节点也要加入到path中 // 这才到了叶子节点 if (cur-left NULL cur-right NULL) { string sPath; for (int i 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: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (root NULL) return result; traversal(root, path, result); return result; } };404.左叶子之和递归三部曲1.确定函数的参数和返回值传入当前节点返回数值之和2.确定终止条件如果遍历到空节点左子数一定为空3.确定单层递归的逻辑遇到左叶子节点时记录数值然后通过递归求左子数左叶子和和右子树左叶子之和相加就是整个树的左叶子之和/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ 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); // 右 int sum leftValue rightValue; // 中 return sum; } };222.完全二叉树的节点个数用层序遍历很好做/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int countNodes(TreeNode* root) { queueTreeNode* que; if (root ! NULL) que.push(root); int result 0; while (!que.empty()) { int size que.size(); for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); result; // 记录节点数量 if (node-left) que.push(node-left); if (node-right) que.push(node-right); } } return result; } };