做个人网站用什么程序,如何制作微信小程序店铺,申请注册商标需要多少钱,网站主机的类型Leetcode 101-平衡二叉树 文章目录 Leetcode 101-平衡二叉树题目描述解题思路 Leetcode 257-二叉树的所有路径题目描述解题思路 Leetcode 404-左叶子之和题目描述解题思路 Leetcode 222-完全二叉树的节点个数题目描述解题思路 题目描述
https://leetcode.cn/problems/balanced…Leetcode 101-平衡二叉树 文章目录 Leetcode 101-平衡二叉树题目描述解题思路 Leetcode 257-二叉树的所有路径题目描述解题思路 Leetcode 404-左叶子之和题目描述解题思路 Leetcode 222-完全二叉树的节点个数题目描述解题思路 题目描述
https://leetcode.cn/problems/balanced-binary-tree/description/ 解题思路
二叉树节点的深度是指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度是指从该节点到叶子节点的最长简单路径边的条数。
这道题我们使用递归采用后序遍历的方法不断获得左右节点的高度并在中间节点比较其高度是否符合平衡二叉树的要求
class Solution {
public:int getHight(TreeNode* root) {if (root nullptr) return 0;int leftHeight getHight(root-left);if (leftHeight -1) return -1;int rightHeight getHight(root-right);if (rightHeight -1) return -1;int result;if (abs(leftHeight - rightHeight) 1) result -1;else result 1 max(leftHeight , rightHeight); return result;}bool isBalanced(TreeNode* root) {return getHight(root) -1 ? false : true;}
};Leetcode 257-二叉树的所有路径
题目描述
https://leetcode.cn/problems/binary-tree-paths/description/ 解题思路
采用前序算法依次遍历
class Solution {
public:void tranversal(TreeNode* cur, vectorint path, vectorstring result) {path.push_back(cur-val);//中if (cur-left nullptr cur-right nullptr) {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) {tranversal(cur-left, path, result);path.pop_back();//回溯}if (cur-right) {tranversal(cur-right, path, result);path.pop_back();//回溯}}vectorstring binaryTreePaths(TreeNode* root) {vectorstringresult;vectorintpath;if (root nullptr)return result;tranversal(root, path, result);return result;}
};Leetcode 404-左叶子之和
题目描述 解题思路
叶子节点的左右子节点都为 nullptr左叶子节点指的是该叶子节点是父节点的左节点。
采用递归后序遍历的方式解决
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root nullptr) return 0;if (root-left nullptr root-right nullptr) return 0;int leftValue sumOfLeftLeaves(root-left);//左if (root-left root-left-left nullptr root-left-right nullptr) leftValue root-left-val;int rightValue sumOfLeftLeaves(root-right);//右int sum leftValue rightValue;//中return sum;}
};Leetcode 222-完全二叉树的节点个数
题目描述 解题思路
完全二叉树的定义是在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1-2^h 个节点。
不考虑完全二叉树的特性仅将其当作普通二叉树采用后序遍历的代码为
class Solution {
public:int countNodes(TreeNode* root) {if (root nullptr) return 0;int leftNode countNodes(root-left);int rightNode countNodes(root-right);int sum leftNode rightNode 1;return sum;}
};此时我们将所有节点都遍历了一遍因此时间复杂度为 O ( n ) O(n) O(n)
为了降低时间复杂度我们可以利用完全二叉树的特性即对于满二叉树其节点个数为(2^n-1)在遍历过程中仅仅遍历两侧的节点从而可以降低时间复杂度
class Solution {
public:int countNodes(TreeNode* root) {if (root nullptr) return 0;TreeNode* left root-left;TreeNode* right root-right;int leftDepth 1, rightDepth 1;while (left) {//遍历左侧深度left left-left;leftDepth;}while (right) {//遍历右侧深度right right-right;rightDepth;}if (leftDepth rightDepth)return (pow(2, leftDepth) - 1);//如果为满二叉树则根据公式直接计算节点个数int leftNum countNodes(root-left);int rightNum countNodes(root-right);int sum leftNum rightNum 1;return sum;}
};
