leetcode刷题 | 关于二叉树的题型总结1

leetcode刷题 | 关于二叉树的题型总结1

题目连接

919. 完全二叉树插入器 - 力扣（LeetCode）

515. 在每个树行中找最大值 - 力扣（LeetCode）

513. 找树左下角的值 - 力扣（LeetCode）

199. 二叉树的右视图 - 力扣（LeetCode）

814. 二叉树剪枝 - 力扣（LeetCode）

297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

完全二叉树插入器

class CBTInserter {TreeNode root;// 存入不完整结构的节点Deque<TreeNode> 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 {List<Integer> res = new ArrayList();public List<Integer> 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,depth+1);if(root.right!=null) dfs(root.right,depth+1);}
}

层序遍历，层序遍历具有通用性，在之后几道题中都可以这么做

class Solution {  public List<Integer> largestValues(TreeNode root) {List<Integer> res = new ArrayList();Deque<TreeNode> 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;Deque<TreeNode> deq = new ArrayDeque();deq.add(root);int res = root.val;while(!deq.isEmpty()){int size = deq.size();for(int i = 0;i<size;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 List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null) return res;Deque<TreeNode> deq = new ArrayDeque<>();deq.add(root);while (!deq.isEmpty()){int size = deq.size();for (int i = 0;i<size;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 "";Deque<TreeNode> 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(",");Deque<TreeNode> 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(",");// 速度更快List<String> nodes = new LinkedList<>(Arrays.asList(strings));return totree(nodes);}public TreeNode totree(List<String> 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;}
}