买衣服网站排行榜前十名_网站收录系统_鞍山做网站的公司_网络营销策划总结

其他:

今日总结
往期打卡

---

110. 平衡二叉树

跳转: 110. 平衡二叉树

学习: 代码随想录公开讲解

问题:

给定一个二叉树，判断它是否是 平衡二叉树

平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。
提示：

• 树中的节点数在范围 [0, 5000] 内
• $-10^4<=Node.val<=10^4$

思路:

平衡二叉树左右子树高度差不超过1
这题要求高度差,所以应该使用后序遍历,毕竟只有先知道高度才能进一步比较.

复杂度:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

代码(递归法):

class Solution {int deep(TreeNode root,int deep){if(root==null) return deep;int a = deep(root.left,deep+1);int b = deep(root.right,deep+1);if(Math.abs(a-b)>1) return -1;return Math.max(a,b);}public boolean isBalanced(TreeNode root) {return deep(root,1)>0;}
}

代码(迭代法):

class Solution {public boolean isBalanced(TreeNode root) {if (root == null) return true;Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode tmp = stack.pop();if (tmp == null) {tmp = stack.pop();int a = tmp.left==null?0:tmp.left.val;int b = tmp.right==null?0:tmp.right.val;if(Math.abs(a-b)>1) return false;tmp.val = Math.max(a,b)+1;} else {stack.push(tmp);stack.push(null);if (tmp.right != null)stack.push(tmp.right);if (tmp.left != null)stack.push(tmp.left);}}return true;}
}

---

257. 二叉树的所有路径

跳转: 257. 二叉树的所有路径

学习: 代码随想录公开讲解

问题:

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

提示：

• 树中节点的数目在范围 [1, 100] 内
• -100 <= Node.val <= 100

思路:

这道题是只要遍历到叶子节点就存储一下路径,所以用前序遍历先判断是否为叶子节点比较合适.

复杂度:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

代码(递归回溯):

class Solution {List<String> ans = new ArrayList<>();void getPath(TreeNode root, StringBuilder s) {if (root == null)return;String tmp = Integer.toString(root.val);if (root.left == null && root.right == null) {ans.add(s.append(tmp).toString());s.delete(s.length() - tmp.length(), s.length());return;}if (root.left != null) {s.append(tmp);s.append("->");getPath(root.left, s);s.delete(s.length() - 2 - tmp.length(), s.length());}if (root.right != null) {s.append(tmp);s.append("->");getPath(root.right, s);s.delete(s.length() - 2 - tmp.length(), s.length());}}public List<String> binaryTreePaths(TreeNode root) {getPath(root, new StringBuilder());return ans;}
}

代码(迭代法):

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> ans = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();Stack<String> str = new Stack<>();stack.push(root);str.push(Integer.toString(root.val));while (!stack.isEmpty()) {TreeNode tmp = stack.pop();String s = str.pop();if (tmp.left == null && tmp.right == null) {ans.add(s);continue;}if (tmp.right != null) {stack.push(tmp.right);str.push(s + "->" + tmp.right.val);}if (tmp.left != null) {stack.push(tmp.left);str.push(s + "->" + tmp.left.val);}}return ans;}
}

---

404. 左叶子之和

跳转: 404. 左叶子之和

学习: 代码随想录公开讲解

问题:

给定二叉树的根节点 root ，返回所有左叶子之和。

提示:

• 节点数在 [1, 1000] 范围内
• -1000 <= Node.val <= 1000

思路:

这题只需要判断每个节点的左子节点是不是叶子节点就好了,前中后序甚至层序遍历都可以做.

复杂度:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

代码(前序递归):

class Solution {int ans = 0;void handle(TreeNode root){if(root==null) return;TreeNode tmp = root.left;if(tmp!=null){if(tmp.left==null&&tmp.right==null)ans+=root.left.val;else handle(root.left);}handle(root.right);}public int sumOfLeftLeaves(TreeNode root) {handle(root);return ans;}
}

代码(中序迭代):

class Solution {public int sumOfLeftLeaves(TreeNode root) {int ans = 0;Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {while (root!=null) {stack.push(root);root = root.left;if(root==null) break;if (root.left == null && root.right == null) {ans += root.val;}}root = stack.pop();root = root.right;}return ans;}
}

---

222. 完全二叉树的节点个数

跳转: 222. 完全二叉树的节点个数

学习: 代码随想录公开讲解

问题:

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。

提示：

• 树中节点的数目范围是[0, 5 * 104]
• 0 <= Node.val <= 5 * 104
• 题目数据保证输入的树是 完全二叉树

进阶： 遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

思路:

遍历计数即可,前中后层序都可以

当然,因为是完全二叉树,所以可以利用完全二叉树的性质来简化遍历

因为完全二叉树紧密排列,所以其左右子树一定至少有一个满二叉树,如果两颗都是满二叉树就用公式2^n-1,否则继续分左右子树
可以算作是一种二分,如果数据量大对时间效率的提升还是很可观的

复杂度:

• 时间复杂度：O(n)
• 空间复杂度：O(log n)

代码(遍历递归):

class Solution {int getChildren(TreeNode root){if(root==null) return 0;int a = getChildren(root.left);int b = getChildren(root.right);return a+b+1;}public int countNodes(TreeNode root) {return getChildren(root);}
}

复杂度:

• 时间复杂度：O(log n × log n)
• 空间复杂度：O(log n)

代码(优化递归):

class Solution {public int countNodes(TreeNode root) {if (root == null)return 0;TreeNode left = root.left;TreeNode right = root.right;int leftDepth = 0, rightDepth = 0; while (left != null) { left = left.left;leftDepth++;}while (right != null) { right = right.right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1;}return countNodes(root.left) + countNodes(root.right) + 1;}
}

---

3375. 使数组的值全部为 K 的最少操作次数(每日一题)

跳转: 3375. 使数组的值全部为 K 的最少操作次数

问题

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有 严格大于 h 的整数值都 相等 ，那么我们称整数 h 是 合法的 。

比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个 合法 整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是 合法 整数。

你可以对 nums 执行以下操作：

• 选择一个整数 h ，它对于 当前 nums 中的值是合法的。
• 对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。

你的目标是将 nums 中的所有元素都变为 k ，请你返回 最少 操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100
  

思路:

由题,每次操作可以将最大的整数转化成第二大的整数.
并且只能从大到小进行转换.

使数组值全部为k其实就是让我们求数组中有多少种比k大的整数.
并且如果存在比k小的数一定不合法.

故这题直接使用哈希计数,并判断一下非法情况即可

复杂度:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

代码:

class Solution {public int minOperations(int[] nums, int k) {int[] hash = new int[101];int ans = 0;for (int i : nums) {if (i < k)return -1;if (i!=k&&hash[i] == 0) {ans++;hash[i]++;}}return ans;}
}

---

总结

练习了二叉树的遍历,复习了平衡二叉树,完全二叉树,满二叉树等特殊二叉树的性质

往期打卡

代码随想录算法训练营第一天

代码随想录算法训练营第二天

代码随想录算法训练营第三天

代码随想录算法训练营第四天

代码随想录算法训练营周末一

代码随想录算法训练营第五天

代码随想录算法训练营第六天

代码随想录算法训练营第七天

代码随想录算法训练营第八天

代码随想录算法训练营第九天

代码随想录算法训练营第十天

代码随想录算法训练营周末二

代码随想录算法训练营第十一天

代码随想录算法训练营第十二天