株洲网站建设,全屋设计师需要学什么,口碑营销的定义,app公司简介范文大全leetcode刷题 | 关于二叉树的题型总结1 文章目录leetcode刷题 | 关于二叉树的题型总结1题目连接完全二叉树插入器在每个树行中找最大值找树左下角的值二叉树的右视图二叉树剪枝题目连接
919. 完全二叉树插入器 - 力扣#xff08;LeetCode#xff09;
515. 在每个树行中找最…leetcode刷题 | 关于二叉树的题型总结1 文章目录leetcode刷题 | 关于二叉树的题型总结1题目连接完全二叉树插入器在每个树行中找最大值找树左下角的值二叉树的右视图二叉树剪枝题目连接
919. 完全二叉树插入器 - 力扣LeetCode
515. 在每个树行中找最大值 - 力扣LeetCode
513. 找树左下角的值 - 力扣LeetCode
199. 二叉树的右视图 - 力扣LeetCode
814. 二叉树剪枝 - 力扣LeetCode
297. 二叉树的序列化与反序列化 - 力扣LeetCode
完全二叉树插入器
class CBTInserter {TreeNode root;// 存入不完整结构的节点DequeTreeNode deq;public CBTInserter(TreeNode root) {this.root root;deq new ArrayDeque();//添加到队列尾部deq.offer(root);while(deq.peek().left ! null deq.peek().right ! null){TreeNode temp deq.poll();deq.offer(temp.left);deq.offer(temp.right);} }public int insert(int v) {TreeNode node deq.peek();if(node.left null) node.left new TreeNode(v);else{node.right new TreeNode(v);deq.poll();deq.offer(node.left);deq.offer(node.right);}return node.val;}public TreeNode get_root() {return root;}
}在每个树行中找最大值
dfs解法按照中左右顺序遍历
class Solution {ListInteger res new ArrayList();public ListInteger largestValues(TreeNode root) {dfs(root,0);return res;}public void dfs(TreeNode root,int depth){if(root null) return;if(res.size() depth){res.add(root.val);}res.set(depth,Math.max(root.val,res.get(depth)));if(root.left ! null) dfs(root.left,depth1);if(root.right!null) dfs(root.right,depth1);}
}层序遍历层序遍历具有通用性在之后几道题中都可以这么做
class Solution { public ListInteger largestValues(TreeNode root) {ListInteger res new ArrayList();DequeTreeNode deq new ArrayDeque();if(root null) return res;deq.add(root);while(!deq.isEmpty()){int size deq.size();int temp Integer.MIN_VALUE;while(size--0){TreeNode node deq.poll();temp Math.max(temp,node.val);if(node.left ! null) deq.add(node.left);if(node.right ! null) deq.add(node.right);}res.add(temp);}return res; }
}找树左下角的值
class Solution {public int findBottomLeftValue(TreeNode root) {if(root null) return -1;DequeTreeNode deq new ArrayDeque();deq.add(root);int res root.val;while(!deq.isEmpty()){int size deq.size();for(int i 0;isize;i){TreeNode node deq.poll();if(i 0) res node.val;if(node.left !null) deq.add(node.left);if(node.right ! null) deq.add(node.right);}}return res;}
}二叉树的右视图
class Solution {public ListInteger rightSideView(TreeNode root) {ListInteger res new ArrayList();if(root null) return res;DequeTreeNode deq new ArrayDeque();deq.add(root);while (!deq.isEmpty()){int size deq.size();for (int i 0;isize;i){TreeNode node deq.poll();if (i size-1) res.add(node.val);if (node.left ! null) deq.add(node.left);if (node.right ! null) deq.add(node.right);}}return res;}
}二叉树剪枝
递归结束条件左子树为空右子树为空当前节点的值为 0同时满足时才表示以当前节点为根二叉树的所有节点都为 0需要将这棵子树移除返回空
class Solution {public TreeNode pruneTree(TreeNode root) {if (root null) return null;root.left pruneTree(root.left);root.right pruneTree(root.right);if (root.left null root.right null root.val 0) return null;return root;}
}DFS从评论区大佬的评论里知道了StringJoiner类做一个简单的解释 StringJoiner是java.util包下的一个工具类jdk1.8出来的 作用是在构造字符串时可以自动添加前缀、后缀及分隔符而不需要自己去实现这些添加字符的逻辑 StringJoiner sj new StringJoiner(“”, “[”, “]”); 代表每一个字符的后缀为前缀开始为[ 后缀结束为 ] 如果 sj.add(“1”).add(“2”).add(“3”); 那么toString() 输出[1,2,3] import java.util.*;
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if (root null) return ;DequeTreeNode deq new ArrayDeque();// 可以提供后缀的末尾StringJoiner sj new StringJoiner(,);deq.offer(root);sj.add(Integer.toString(root.val));while (!deq.isEmpty()){int size deq.size();while (size-- 0){TreeNode node deq.poll();if (node.left ! null){deq.add(node.left);sj.add(Integer.toString(node.left.val));}else sj.add(null);if (node.right ! null){deq.add(node.right);sj.add(Integer.toString(node.right.val));}else sj.add(null);}}return sj.toString();}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if (data ) return null;String[] strings data.split(,);DequeTreeNode deq new ArrayDeque();TreeNode root new TreeNode(Integer.parseInt(strings[0]));deq.add(root);int index 1; //定位当前位置遍历顺序为中左右int l strings.length;while(index l){TreeNode node deq.poll();if (!strings[index].equals(null)){TreeNode left new TreeNode(Integer.parseInt(strings[index]));node.left left;deq.add(left);}index; //找右节点if (index l !strings[index].equals(null)){TreeNode right new TreeNode(Integer.parseInt(strings[index]));node.right right;deq.add(right);}index; //找左节点}return root;}
}BFS解法
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {StringBuilder stringBuilder new StringBuilder();return appendstr(root,stringBuilder).toString();}private StringBuilder appendstr(TreeNode node,StringBuilder stringBuilder){if (node null) return stringBuilder.append(null,);else {// 中左右stringBuilder.append(Integer.toString(node.val),);stringBuilder appendstr(node.left,stringBuilder);stringBuilder appendstr(node.right,stringBuilder);}return stringBuilder;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] strings data.split(,);// 速度更快ListString nodes new LinkedList(Arrays.asList(strings));return totree(nodes);}public TreeNode totree(ListString nodes){if (nodes.get(0).equals(null)){nodes.remove(0);return null;}TreeNode root new TreeNode(Integer.parseInt(nodes.get(0)));nodes.remove(0);root.left totree(nodes);root.right totree(nodes);return root;}
}
