首页 / 算法 / 每日算法11_2020-11-17
每日算法11_2020-11-17
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了每日算法11_2020-11-17，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9673字，纯文字阅读大概需要14分钟。
内容图文
题目一
101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
我的答案
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
// 检查传过来的左右节点的值左右子树是否相同
public static boolean check(TreeNode leftNode, TreeNode rightNode){
if(leftNode == null && rightNode == null) return true;
if(leftNode == null || rightNode == null) return false;
// 检查
// 左右节点的值
// 左节点的左子树与右节点的右子树
// 左节点的右子树与右节点的左子树
// 是否相等
return leftNode.val == rightNode.val &&
check(leftNode.left, rightNode.right) &&
check(leftNode.right, rightNode.left);
}
}
复杂度分析
假设树上一共 n 个节点。
时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。
我认为的迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
TreeNode rootroot = root; // 用于标记最顶层根节点
TreeNode root2 = root; // 复制一份引用
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
// 一个栈装左子树，一个栈装右子树
// 就是一边直冲最底层左子树，一边直冲最右右子树
// 就是类似中序遍历一样，左右子树只不过是相反的而已
while(!stack.isEmpty() || !stack2.isEmpty() || root != null || root2 != null){
int leftVal = 0, rightVal = 0;
while(root != null){
stack.push(root); // 把本身放进栈
root = root.left;
// 出这个循环说明达到最左边的节点了
}
while(root2 != null){
stack2.push(root2); // 把本身放进栈
root2 = root2.right;
// 出这个循环说明达到最右边的节点了
}
// 弹出最上面的节点（即为上行代码比较值的节点）
root = stack.pop();
root2 = stack2.pop();
leftVal = root.val; // 记录值
rightVal = root2.val; // 记录值
System.out.println(leftVal + " - " + rightVal);
// 在判断值前先判断两个栈内的元素是否一样多，对称树应该时一样多的
if(stack.size() != stack2.size()) return false;
if (leftVal != rightVal) return false; // 判断左右值，不同即false
// 有一个回到顶层节点另一个却没回到顶层节点时直接返回false
if(root == rootroot && root2 != rootroot) return false;
if(root2 == rootroot && root != rootroot) return false;
// 判断是否回到了最顶层根节点
if(root == root2) return true; // 回到了说明左右子树一样，这时就必要再往下判断了
// 没回到最顶层根节点，就要判断左子树的右节点和右子树的左节点值是否相同
root = root.right;
root2 = root2.left;
}
return stack.isEmpty() && stack2.isEmpty();
}
}
正确的迭代
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode u, TreeNode v) {
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(u);
q.offer(v);
while (!q.isEmpty()) {
u = q.poll();
v = q.poll();
if (u == null && v == null) {
continue;
}
if ((u == null || v == null) || (u.val != v.val)) {
return false;
}
q.offer(u.left);
q.offer(v.right);
q.offer(u.right);
q.offer(v.left);
}
return true;
}
}
复杂度分析
时间复杂度：O(n)，同「递归」。
空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。
题目二
112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
我的答案
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
return root != null && maxValue(root, 0, sum); // 添加进去了说明没有这个路径值，就取反为false
}
public boolean maxValue(TreeNode node, int n, int sum){
if (node == null) return false;
if (node.left == null && node.right == null){
// 说明到叶子节点了，判断此时和会不会等于sum
n += node.val;
return n == sum;
}else{
// 不为null就往下继续找节点
n += node.val;
return maxValue(node.left, n, sum) || maxValue(node.right, n, sum);
}
}
}
广度优先算法
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
Queue<TreeNode> queNode = new LinkedList<TreeNode>();
Queue<Integer> queVal = new LinkedList<Integer>();
queNode.offer(root);
queVal.offer(root.val);
while (!queNode.isEmpty()) {
TreeNode now = queNode.poll();
int temp = queVal.poll();
if (now.left == null && now.right == null) {
if (temp == sum) {
return true;
}
continue;
}
if (now.left != null) {
queNode.offer(now.left);
queVal.offer(now.left.val + temp);
}
if (now.right != null) {
queNode.offer(now.right);
queVal.offer(now.right.val + temp);
}
}
return false;
}
}
复杂度分析
时间复杂度：O(N)，其中 NN 是树的节点数。对每个节点访问一次。
空间复杂度：O(N)，其中 NN 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。
递归
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return sum == root.val;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
复杂度分析
时间复杂度：O(N)，其中 NN 是树的节点数。对每个节点访问一次。
空间复杂度：O(H)，其中 HH 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(\log N)。
题目三
5601. 设计有序流
我的答案
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0 || postorder.length == 0) return null;
// 中序和后序的区别就是，最顶层根节点一个在中间一个在末尾
// 另外后序遍历其实就是从右开始前序遍历而已
ArrayList<Integer> intsIn = new ArrayList<>();
ArrayList<Integer> intsPost = new ArrayList<>();
for (int i = 0; i < inorder.length; i++) {
intsIn.add(inorder[i]);
intsPost.add(postorder[i]);
}
// System.out.println("ints = " + intsIn);
// System.out.println("ints2 = " + intsPost);
TreeNode root = new TreeNode(intsPost.get(intsPost.size()-1));
// 分割左右子树
int rootIndex = intsIn.lastIndexOf(root.val);
// System.out.println(rootIndex);
List<Integer> ints1LeftTree = intsIn.subList(0, rootIndex);
List<Integer> ints1RightTree = intsIn.subList(rootIndex+1, intsIn.size());
List<Integer> ints2LeftTree = intsPost.subList(0, ints1LeftTree.size());
List<Integer> ints2RightTree = intsPost.subList(ints1LeftTree.size(), intsPost.size()-1);
root.left = retTree(ints1LeftTree, ints2LeftTree);
root.right = retTree(ints1RightTree, ints2RightTree);
return root;
}
public TreeNode retTree(List<Integer> intsIn, List<Integer> intsPost){
if(intsPost.size()-1 == -1) return null;
TreeNode root = new TreeNode(intsPost.get(intsPost.size()-1));
int rootIndex = intsIn.lastIndexOf(root.val);
List<Integer> ints1LeftTree = intsIn.subList(0, rootIndex);
List<Integer> ints1RightTree = intsIn.subList(rootIndex+1, intsIn.size());
List<Integer> ints2LeftTree = intsPost.subList(0, ints1LeftTree.size());
List<Integer> ints2RightTree = intsPost.subList(ints1LeftTree.size(), intsPost.size()-1);
root.left = retTree(ints1LeftTree, ints2LeftTree);
root.right = retTree(ints1RightTree, ints2RightTree);
return root;
}
}
递归
class Solution {
int post_idx;
int[] postorder;
int[] inorder;
Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();
public TreeNode helper(int in_left, int in_right) {
// 如果这里没有节点构造二叉树了，就结束
if (in_left > in_right) {
return null;
}
// 选择 post_idx 位置的元素作为当前子树根节点
int root_val = postorder[post_idx];
TreeNode root = new TreeNode(root_val);
// 根据 root 所在位置分成左右两棵子树
int index = idx_map.get(root_val);
// 下标减一
post_idx--;
// 构造右子树
root.right = helper(index + 1, in_right);
// 构造左子树
root.left = helper(in_left, index - 1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
this.inorder = inorder;
// 从后序遍历的最后一个元素开始
post_idx = postorder.length - 1;
// 建立（元素，下标）键值对的哈希表
int idx = 0;
for (Integer val : inorder) {
idx_map.put(val, idx++);
}
return helper(0, inorder.length - 1);
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是树中的节点个数。
空间复杂度：O(n)。我们需要使用 O(n) 的空间存储哈希表，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h <n，所以总空间复杂度为 O(n)。
迭代
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder == null || postorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
int inorderIndex = inorder.length - 1;
for (int i = postorder.length - 2; i >= 0; i--) {
int postorderVal = postorder[i];
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
node.right = new TreeNode(postorderVal);
stack.push(node.right);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex--;
}
node.left = new TreeNode(postorderVal);
stack.push(node.left);
}
}
return root;
}
}
复杂度分析
时间复杂度：O(n)，其中 n是树中的节点个数。
空间复杂度：O(n)，我们需要使用 O(h)（其中 h 是树的高度）的空间存储栈。这里 h <n，所以（在最坏情况下）总空间复杂度为 O(n)。
内容总结
以上是互联网集市为您收集整理的每日算法11_2020-11-17全部内容，希望文章能够帮你解决每日算法11_2020-11-17所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】