算法学习记录～2023.5.3～二叉树Day3～222. 完全二叉树的节点个数 & 110.平衡二叉树 & 257.二叉树的所有路径

2023-06-06 00:43| 来源: 网络整理| 查看: 265

算法学习记录| 2023.X.XX| 章节DayX| 题目号.题目标题 & 题目号.题目标题 222. 完全二叉树的节点个数题目链接思路1：当作普通二叉树常规遍历代码思路2：根据完全二叉树的性质简化遍历次数代码总结 110.平衡二叉树题目链接思路1：递归代码思路2：迭代代码总结 257. 二叉树的所有路径题目链接思路1：递归代码思路2：迭代代码总结

222. 完全二叉树的节点个数题目链接

力扣题目链接

思路1：当作普通二叉树常规遍历

遍历所有节点，不使用完全二叉树的性质，DFS和BFS均可

代码

e.g 递归

class Solution { public: void countNodes(TreeNode* root){ if(!root) return 0; return countNodes(root->left) + countNodes(root->right) + 1; } };

e.g 层序遍历

class Solution { public: int countNodes(TreeNode* root) { queue que; int count = 0; if (root != NULL){ que.push(root); } while(!que.empty()){ int size = que.size(); count += size; for(int i = 0; i public: int countNodes(TreeNode* root) { if (root == NULL) return 0; //递归三步曲第二步的终止条件 TreeNode* left = root -> left; TreeNode* right = root -> right; int leftdepth,rightdepth = 0; while(left){ //左子树深度 left = left -> left; leftdepth++; } while(right){ //右子树深度 right = right -> right; rightdepth++; } if(leftdepth == rightdepth){ //左右子树深度相同则是满二叉树 return (2 right) + 1; //总数 } }; 总结

本题考查了对于完全二叉树的理解，其中将问题分解为满二叉树和其他情况的思路需要学习理解。

110.平衡二叉树题目链接

力扣题目链接

思路1：递归

因为是求高度，所以需要后序遍历。通过递归分别求所有节点的高度，在递归同时不断判断左右子树高度差，如果发现则直接返回-1作为已经不符合要求的标记，不需要继续递归了。

代码 class Solution { public: int getHeight(TreeNode* root){ //设定如果值为-1即已经不是平衡二叉树 if (root == NULL) return 0; int leftHeight = getHeight(root -> left); //左 if (leftHeight == -1) //如果子树已经不是平衡二叉树了那现在更不符合要求 return -1; int rightHeight = getHeight(root -> right); //右 if (rightHeight == -1) return -1; return abs(leftHeight - rightHeight) > 1 ? -1 : max(leftHeight, rightHeight) + 1; //中 } bool isBalanced(TreeNode* root) { return getHeight(root) == -1 ? false : true; } }; 思路2：迭代

在104.二叉树的最大深度中我们可以使用层序遍历来求深度，但是就不能直接用层序遍历来求高度了，这就体现出求高度和求深度的不同。

本题的迭代方式可以先定义一个函数，专门用来求高度。这个函数通过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的最大深度来求的高度）。然后再用栈来模拟后序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合。

此题用迭代法，其实效率很低，因为不能很好的模拟回溯的过程，所以迭代法有很多重复的计算。

由于并不是很优因此第一遍没细看代码 class Solution { private: int getDepth(TreeNode* cur) { stack st; if (cur != NULL) st.push(cur); int depth = 0; // 记录深度 int result = 0; while (!st.empty()) { TreeNode* node = st.top(); if (node != NULL) { st.pop(); st.push(node); // 中 st.push(NULL); depth++; if (node->right) st.push(node->right); // 右 if (node->left) st.push(node->left); // 左 } else { st.pop(); node = st.top(); st.pop(); depth--; } result = result > depth ? result : depth; } return result; } public: bool isBalanced(TreeNode* root) { stack st; if (root == NULL) return true; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); // 中 st.pop(); if (abs(getDepth(node->left) - getDepth(node->right)) > 1) { return false; } if (node->right) st.push(node->right); // 右（空节点不入栈） if (node->left) st.push(node->left); // 左（空节点不入栈） } return true; } }; 总结

此题完全掌握递归其实就可以了，迭代了解思路即可。

257. 二叉树的所有路径题目链接

力扣题目链接

本题涉及到回溯因为需要把路径记录下来，所以需要回溯来回退一个路径再进入另一个路径。因为要求从根节点到叶子节点的路径，所以需要前序遍历，这样才方便父节点指向孩子节点。

思路1：递归递归函数参数以及返回值：要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值 void traversal(TreeNode* cur, vector& path, vector& result) 确定递归终止条件：因为找到叶子节点时就得开始终止处理的逻辑，因此应设置为找到叶子节点时 if (cur->left == NULL && cur->right == NULL) { 终止处理的逻辑 }

接下来就是终止处理的逻辑应该是怎样的。也就是记录路径如何写。

因为使用vector 结构的path来记录路径，所以要把vector 结构的path转为string格式，再把这个string 放进 result里。为什么使用了vector 结构来记录路径呢？因为在下面处理单层递归逻辑的时候，要做回溯，使用vector方便来做回溯。

if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点 string sPath; for (int i = 0; i traversal(cur->left, path, result); } if (cur->right) { traversal(cur->right, path, result); }

path除了加入节点，还需要删除节点，所以需要回溯。回溯与递归是一一对应的。

if (cur->left) { traversal(cur->left, path, result); path.pop_back(); // 回溯 } if (cur->right) { traversal(cur->right, path, result); path.pop_back(); // 回溯 } 代码 class Solution { public: void recPath ( TreeNode* cur, vector& path, vector& result){ path.push_back(cur -> val); //中。由于最后一个节点也需要被记录在path所以写在前面 if ( cur -> left == NULL && cur -> right == NULL){ //找到了叶子节点说明找到了一条路径 string sPath; for (int i = 0; i //左。不为空的话则可以递归 recPath( cur -> left, path, result); path.pop_back(); //回溯 } if ( cur -> right ){ //右。不为空的话则可以递归 recPath( cur -> right, path, result); path.pop_back(); //回溯 } } vector binaryTreePaths(TreeNode* root) { vector result; //因为涉及到->字符所以需要string类型 vector path; //记录路径节点的值 if (root == NULL ) return result; recPath(root, path, result); return result; } }; 思路2：迭代

除了模拟递归需要一个栈，同时还需要一个栈来存放对应的遍历路径

第一次没用迭代法的通用写法写出来，之后试试。或者二刷时候重点再背熟练三种DFS算法的非统一写法代码

前序遍历

class Solution { public: vector binaryTreePaths(TreeNode* root) { stack treeSt;// 保存树的遍历节点 stack pathSt; // 保存遍历路径的节点 vector result; // 保存最终路径集合 if (root == NULL) return result; treeSt.push(root); pathSt.push(to_string(root->val)); while (!treeSt.empty()) { TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点中 string path = pathSt.top();pathSt.pop(); // 取出该节点对应的路径 if (node->left == NULL && node->right == NULL) { // 遇到叶子节点 result.push_back(path); } if (node->right) { // 右 treeSt.push(node->right); pathSt.push(path + "->" + to_string(node->right->val)); } if (node->left) { // 左 treeSt.push(node->left); pathSt.push(path + "->" + to_string(node->left->val)); } } return result; } }; 总结

一刷没有用通用写法写出来迭代遍历，二刷试一下。或者继续熟练DFS三种遍历方式的非统一版迭代方法

【本文地址】

公司简介

联系我们