网站制作设计培训多少钱,沈阳建设工程城乡建设厅,网站设计 wordpress,wordpress编辑模板标题257. 二叉树的所有路径
给你一个二叉树的根节点 root #xff0c;按 任意顺序 #xff0c;返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。 示例 1#xff1a; 输入#xff1a;root [1,2,3,null,5]
输出#xff1a;[1-2-5,按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。 示例 1 输入root [1,2,3,null,5]
输出[1-2-5,1-3]
思路可以采用深度优先遍历将每个节点的val放进当前path然后判断当前节点是否为叶子节点叶子节点则保存当前路径非叶子节点则继续遍历
细节这里findPath的参数path不能用引用因为引用会将有效的路径也push进了一些无效的val后续还要加入裁剪path。
/*** 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:void findPaths(TreeNode* root, string path, vectorstring ret) {if (root ! nullptr) {path to_string(root-val);//判断是否为叶子节点if (root-left nullptr root-right nullptr) { ret.push_back(path); } else {path -; findPaths(root-left, path, ret);findPaths(root-right, path, ret);}}}vectorstring binaryTreePaths(TreeNode* root) {vectorstring ret;findPaths(root, , ret);return ret;}
}; 222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。 示例 1 输入root [1,2,3,4,5,6]
输出6
思路1所有节点正常遍历一遍并计数即可。
进阶遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗
该方法参考了代码随想录
代码随想录 (programmercarl.com)
思路2满二叉树有个特点是只有最后一层可能不是满的且从左到右不会有“间断”。从左右子树来看只有一个子树不是完全满二叉树。对于完全满二叉树可以按2**h-1得到节点数对于不是完全满二叉树的可以一直递归左右子树直到出现空节点或叶子节点。 判断是否为完全满二叉树可以判断 left到底和right到底 两数是否相等。 /*** 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) {//左右子树中最多只有一个子树不是满二叉。//该节点为空或叶子节点if(!root) return 0;else if(!root-left!root-right) return 1;else{int left0,right0;for(TreeNode* noderoot;node;nodenode-left) left;for(TreeNode* noderoot;node;nodenode-right) right;if(leftright) return (1left)-1;else return countNodes(root-left)countNodes(root-right)1;}}
};
左右子树中最多只有一个子树不是满二叉。所以总体的时间复杂度仍然是logn ^ 2
