序列化二叉树&&二叉搜索树的第k个结点&&字符串变形
1、解题思路
队列中不能push空值，所以一旦遇到空，可以push进去一个101，表示空值。
2、代码
import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { private int getDepth(TreeNode node) { if (node == null) { return 0; } else { int l = getDepth(node.left); int r = getDepth(node.right); return l >= r ? l + 1 : r + 1; } } String Serialize(TreeNode root) { if (root == null) { return ""; } StringBuilder stringBuilder = new StringBuilder(); Queue<TreeNode> queue = new ArrayDeque<>(); queue.add(root); int depth = getDepth(root); for (int i = 1; i <= depth; i++) { int size = queue.size(); for (int j = 0; j < size; j++) { TreeNode poll = queue.poll(); if (poll.val == 101) { stringBuilder.append("null,"); queue.add(new TreeNode(101)); queue.add(new TreeNode(101)); } else { stringBuilder.append(poll.val); stringBuilder.append(","); if (poll.left != null) { queue.add(poll.left); } else { queue.add(new TreeNode(101)); } if (poll.right != null) { queue.add(poll.right); } else { queue.add(new TreeNode(101)); } } } } stringBuilder.deleteCharAt(stringBuilder.length() - 1); return stringBuilder.toString(); } private TreeNode TreeNodeHelper(String[] strings, int index) { if (index >= strings.length || strings[index].equals("null")) { return null; } else { TreeNode node = new TreeNode(Integer.parseInt(strings[index])); node.left = TreeNodeHelper(strings, index * 2 + 1); node.right = TreeNodeHelper(strings, index * 2 + 2); return node; } } TreeNode Deserialize(String str) { if (str == null || str.length() == 0) { return null; } String[] split = str.split(","); return TreeNodeHelper(split, 0); } } 复制代码NC81 二叉搜索树的第k个结点
题目链接
1、解题思路
采用先序，然后每遍历一个结点，k值减1，输出k减到0的那个节点就可了。
2、代码
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { private int k; private TreeNode preOrder(TreeNode pRoot) { if (pRoot == null) { return null; } TreeNode node = preOrder(pRoot.left); if (node != null) { return node; } this.k--; if (this.k == 0) { return pRoot; } TreeNode node1 = preOrder(pRoot.right); if (node1 != null) { return node1; } else { return null; } } TreeNode KthNode(TreeNode pRoot, int k) { this.k = k; return preOrder(pRoot); } } 复制代码NC89 字符串变形
题目链接
1、解题思路
普通字符串处理。
2、代码
import java.util.*; public class Solution { private String convert(String s) { StringBuilder stringBuilder = new StringBuilder(s).reverse(); char[] chars = stringBuilder.toString().toCharArray(); for (int i = 0; i < chars.length; i++) { if (chars[i] >= 'a' && chars[i] <= 'z') { chars[i] -= 32; } else { chars[i] += 32; } } return new String(chars); } public String trans(String s, int n) { StringBuilder stringBuilder = new StringBuilder(); s = new StringBuilder(s).reverse().toString(); int index = 0; int len = s.length(); while (index < len) { if (s.charAt(index) == ' ') { stringBuilder.append(' '); index++; } else { int start = index; while (index < len && s.charAt(index) != ' ') { index++; } stringBuilder.append(convert(s.substring(start, index))); } } return stringBuilder.toString(); } }
作者：jdq8576
链接：https://juejin.cn/post/7025778680366366750