leetcode刷题 | 关于二叉树的题型总结1
题目连接
515. 在每个树行中找最大值 - 力扣（LeetCode）
297. 二叉树的序列化与反序列化 - 力扣（LeetCode）
完全二叉树插入器
classCBTInserter {
TreeNoderoot;
// 存入不完整结构的节点
Deque<TreeNode>deq;
publicCBTInserter(TreeNoderoot) {
this.root=root;
deq=newArrayDeque();
//添加到队列尾部
deq.offer(root);
while(deq.peek().left!=null&&deq.peek().right!=null){
TreeNodetemp=deq.poll();
deq.offer(temp.left);
deq.offer(temp.right);
}
}
publicintinsert(intv) {
TreeNodenode=deq.peek();
if(node.left==null) node.left=newTreeNode(v);
else{
node.right=newTreeNode(v);
deq.poll();
deq.offer(node.left);
deq.offer(node.right);
}
returnnode.val;
}
publicTreeNodeget_root() {
returnroot;
}
}
在每个树行中找最大值
dfs解法，按照中左右顺序遍历
classSolution {
List<Integer>res=newArrayList();
publicList<Integer>largestValues(TreeNoderoot) {
dfs(root,0);
returnres;
}
publicvoiddfs(TreeNoderoot,intdepth){
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,depth+1);
if(root.right!=null) dfs(root.right,depth+1);
}
}
层序遍历，层序遍历具有通用性，在之后几道题中都可以这么做
classSolution {
publicList<Integer>largestValues(TreeNoderoot) {
List<Integer>res=newArrayList();
Deque<TreeNode>deq=newArrayDeque();
if(root==null) returnres;
deq.add(root);
while(!deq.isEmpty()){
intsize=deq.size();
inttemp=Integer.MIN_VALUE;
while(size-->0){
TreeNodenode=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);
}
returnres;
}
}
找树左下角的值
classSolution {
publicintfindBottomLeftValue(TreeNoderoot) {
if(root==null) return-1;
Deque<TreeNode>deq=newArrayDeque();
deq.add(root);
intres=root.val;
while(!deq.isEmpty()){
intsize=deq.size();
for(inti=0;i<size;i++){
TreeNodenode=deq.poll();
if(i==0) res=node.val;
if(node.left!=null) deq.add(node.left);
if(node.right!=null) deq.add(node.right);
}
}
returnres;
}
}
二叉树的右视图
classSolution {
publicList<Integer>rightSideView(TreeNoderoot) {
List<Integer>res=newArrayList<>();
if(root==null) returnres;
Deque<TreeNode>deq=newArrayDeque<>();
deq.add(root);
while (!deq.isEmpty()){
intsize=deq.size();
for (inti=0;i<size;i++){
TreeNodenode=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);
}
}
returnres;
}
}
二叉树剪枝
递归结束条件：左子树为空，右子树为空，当前节点的值为 0，同时满足时，才表示以当前节点为根二叉树的所有节点都为 0，需要将这棵子树移除，返回空
classSolution {
publicTreeNodepruneTree(TreeNoderoot) {
if (root==null) returnnull;
root.left=pruneTree(root.left);
root.right=pruneTree(root.right);
if (root.left==null&&root.right==null&&root.val==0) returnnull;
returnroot;
}
}
DFS，从评论区大佬的评论里知道了StringJoiner类，做一个简单的解释
StringJoiner是java.util包下的一个工具类，jdk1.8出来的
作用是在构造字符串时，可以自动添加前缀、后缀及分隔符，而不需要自己去实现这些添加字符的逻辑
StringJoiner sj = new StringJoiner("，", "[", "]");
代表每一个字符的后缀为，前缀开始为[ ， 后缀结束为 ]
如果 sj.add("1").add("2").add("3");
那么toString() 输出：[1,2,3]
importjava.util.*;
publicclassCodec {
// Encodes a tree to a single string.
publicStringserialize(TreeNoderoot) {
if (root==null) return"";
Deque<TreeNode>deq=newArrayDeque<>();
// 可以提供后缀的末尾
StringJoinersj=newStringJoiner(",");
deq.offer(root);
sj.add(Integer.toString(root.val));
while (!deq.isEmpty()){
intsize=deq.size();
while (size-->0){
TreeNodenode=deq.poll();
if (node.left!=null){
deq.add(node.left);
sj.add(Integer.toString(node.left.val));
}elsesj.add("null");
if (node.right!=null){
deq.add(node.right);
sj.add(Integer.toString(node.right.val));
}elsesj.add("null");
}
}
returnsj.toString();
}
// Decodes your encoded data to tree.
publicTreeNodedeserialize(Stringdata) {
if (data=="") returnnull;
String[] strings=data.split(",");
Deque<TreeNode>deq=newArrayDeque<>();
TreeNoderoot=newTreeNode(Integer.parseInt(strings[0]));
deq.add(root);
intindex=1; //定位当前位置，遍历顺序为中左右
intl=strings.length;
while(index<l){
TreeNodenode=deq.poll();
if (!strings[index].equals("null")){
TreeNodeleft=newTreeNode(Integer.parseInt(strings[index]));
node.left=left;
deq.add(left);
}
index++; //找右节点
if (index<l&&!strings[index].equals("null")){
TreeNoderight=newTreeNode(Integer.parseInt(strings[index]));
node.right=right;
deq.add(right);
}
index++; //找左节点
}
returnroot;
}
}
BFS解法
publicclassCodec {
// Encodes a tree to a single string.
publicStringserialize(TreeNoderoot) {
StringBuilderstringBuilder=newStringBuilder();
returnappendstr(root,stringBuilder).toString();
}
privateStringBuilderappendstr(TreeNodenode,StringBuilderstringBuilder){
if (node==null) returnstringBuilder.append("null,");
else {
// 中左右
stringBuilder.append(Integer.toString(node.val)+",");
stringBuilder=appendstr(node.left,stringBuilder);
stringBuilder=appendstr(node.right,stringBuilder);
}
returnstringBuilder;
}
// Decodes your encoded data to tree.
publicTreeNodedeserialize(Stringdata) {
String[] strings=data.split(",");
// 速度更快
List<String>nodes=newLinkedList<>(Arrays.asList(strings));
returntotree(nodes);
}
publicTreeNodetotree(List<String>nodes){
if (nodes.get(0).equals("null")){
nodes.remove(0);
return null;
}
TreeNoderoot=newTreeNode(Integer.parseInt(nodes.get(0)));
nodes.remove(0);
root.left=totree(nodes);
root.right=totree(nodes);
returnroot;
}
}
