icp主体备案号和网站备案号,天津平台网站建设推荐,宁波seo推广服务,国家企业查询官网目录
1 543. 二叉树的直径
2 102. 二叉树的层序遍历
3 108. 将有序数组转换为二叉搜索树 菜鸟做题#xff0c;语言是 C 1 543. 二叉树的直径
这道题和 124. 二叉树中的最大路径和 太像了
题眼#xff1a;二叉树的 直径 是指树中任意两个节点之间 最长路径的长度 。…目录
1 543. 二叉树的直径
2 102. 二叉树的层序遍历
3 108. 将有序数组转换为二叉搜索树 菜鸟做题语言是 C 1 543. 二叉树的直径
这道题和 124. 二叉树中的最大路径和 太像了
题眼二叉树的 直径 是指树中任意两个节点之间 最长路径的长度 。 简而言之就是找出一条路径且这条路径上的节点最多。 解题思路
从下往上遍历二叉树当前子树中的最长路径 1 左子树中的最长路径 右子树中的最长路径向父节点自荐当前子树中的最长路径 1 max(左子树中的最长路径右子树中的最长路径) 为什么必须从 “左子树中的最长路径” 和 “右子树中的最长路径” 中选一个不能都要吗当然不行。我们要的是一条笔直的路径如果左右子树都带上那不就分叉了吗。 思路说明图 对于绿色节点在它作为根节点的子树中最长路径 1 左子树中的最长路径 右子树中的最长路径绿色节点左子节点向蓝色节点父节点自荐自荐的最长路径 1 max(左子树中的最长路径右子树中的最长路径)。对于蓝色节点在它作为根节点的子树中最长路径 1 左子树中的最长路径 右子树中的最长路径。以此类推。
class Solution {
public:int ans 1;int helper(TreeNode * root) {if (!root) return 0;int ltree helper(root-left);int rtree helper(root-right);ans max(ans, 1 ltree rtree);return 1 max(ltree, rtree);}int diameterOfBinaryTree(TreeNode* root) {helper(root);return ans - 1;}
};
说明我们算的其实是最多节点数而路径长度是边的条数因此需要减一
return ans - 1; 2 102. 二叉树的层序遍历
是循环不是递归
层序遍历逐层地从左到右访问所有节点。 解题思路
出队从左到右遍历当前层中的每个节点入队将每个节点的左右子节点存入队列中出队从左到右遍历左右子节点即下一层中的每个节点
具体代码
① 循环条件当队列中还有节点没有被遍历时即队列长度不为 0 时。
while (q.size()) {}
② 遍历某一层中的所有节点
int currentLevelSize q.size();
for (int i 0; i currentLevelSize; i) {TreeNode * node q.front();q.pop();// ...
} 此时队列的大小等于当前层中的节点个数。 ③ 存入每个节点的左右子节点即下一层中的所有节点。
if (node-left) q.push(node-left);
if (node-right) q.push(node-right); 只有节点不为空时才需要被访问。 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {if (!root) return {};vectorvectorint ans;queueTreeNode * q;q.push(root);while (q.size()) {int currentLevelSize q.size();ans.push_back(vectorint ());for (int i 0; i currentLevelSize; i) {TreeNode * node q.front();q.pop();ans.back().push_back(node-val);if (node-left) q.push(node-left);if (node-right) q.push(node-right);}}return ans;}
}; 3 108. 将有序数组转换为二叉搜索树
与对 105. 从前序与中序遍历序列构造二叉树 的理解有一点点像
可以理解成将有序数组视为中序遍历的结果并将其还原回二叉树。
中序遍历的结果数组的特点(左子树根节点右子树)
题眼高度平衡二叉树 是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。因此我们每次都取数组区间的中间值为根节点代码如下
int mid (left right) / 2;
完整代码
class Solution {
public:TreeNode* helper(vectorint nums, int left, int right) {if (left right) return nullptr;int mid (left right) / 2;TreeNode* root new TreeNode(nums[mid]);root-left helper(nums, left, mid - 1);root-right helper(nums, mid 1, right);return root;}TreeNode* sortedArrayToBST(vectorint nums) {return helper(nums, 0, nums.size() - 1);}
};
