与二叉树有关的编程题的Java代码实现
2024-09-13 21:13:34
该文章几乎包含了所有与二叉树相关的基础面试题，其中包括二叉树的四种遍历方法：前序遍历，中序遍历，后续遍历，层次遍历。
算法题包括：
二叉树的序列化和反序列化
给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中， 按结点数值大小顺序第三个结点的值为4。
package test; import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue; import org.junit.Test; class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null; public TreeNode(int val) {
this.val = val; } } public class Solution {
/**
* 二叉树的前序序列化
*
* @param root
* @return
*/
String Serialize(TreeNode root) {
if (root == null)
return null;
StringBuilder str = new StringBuilder();
SerializeRe(root, str);
return str.toString();
} /**
* 二叉树的前序序列化递归方法
*
* @param root
* @param str
*/
public void SerializeRe(TreeNode root, StringBuilder str) {
if (root == null) {
str.append("#,");
return;
} else {
str.append(root.val);
str.append(",");
SerializeRe(root.left, str);
SerializeRe(root.right, str);
}
return;
} /**
* 前序反序列化
*
* @param str
* @return
*/
TreeNode Deserialize(String str) {
if (str == null || str.length() == 0 || str.equals("#"))
return null;
String[] value = str.split(",");
return DeserializeRe(value);
} int index = 0; /**
* 前序反序列化递归方法
*
* @param str
* @return
*/
public TreeNode DeserializeRe(String[] str) {
TreeNode root = new TreeNode(-1);
if (str[index].equals("#") || index > str.length) {
return null;
}
root.val = Integer.valueOf(str[index]);
index++;
root.left = DeserializeRe(str);
index++;
root.right = DeserializeRe(str);
return root;
} /**
* 根据数组从上到下构造一棵二叉树（即完全二叉树）
*
* @param a
* @param index
* @return
*/
public TreeNode buildTreeLevel(int[] a) {
if (a == null || a.length == 0)
return null;
return buildTreeLevelRe(a, 0);
} private TreeNode buildTreeLevelRe(int[] a, int index) {
TreeNode root = new TreeNode(-1);
root.val = a[index];
if (index * 2 + 1 <= a.length - 1) {
root.left = buildTreeLevelRe(a, index * 2 + 1);
}
if (index * 2 + 2 <= a.length - 1) {
root.right = buildTreeLevelRe(a, index * 2 + 2);
}
return root;
} /**
* 前序遍历二叉树
*
* @param root
*/
public void preOderTree(TreeNode root) {
if (root == null)
return;
System.out.println(root.val);
preOderTree(root.left);
preOderTree(root.right);
return;
} /**
* 中序遍历二叉树
*
* @param root
*/
public void inOderTree(TreeNode root) {
if (root == null)
return;
inOderTree(root.left);
System.out.println(root.val);
inOderTree(root.right);
return;
} /**
* 后序遍历二叉树
*
* @param root
*/
public void postOderTree(TreeNode root) {
if (root == null)
return;
postOderTree(root.left);
postOderTree(root.right);
System.out.println(root.val);
return;
} /**
* 层次遍历二叉树
*
* @param root
*/
public void levelOderTree(TreeNode root) {
if (root == null)
return;
Queue<TreeNode> nodes = new LinkedList<TreeNode>();
nodes.add(root);
while (!nodes.isEmpty()) {
TreeNode node = nodes.poll();
System.out.println(node.val);
if (node.left != null) {
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
}
}
} /**
* 给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中， 按结点数值大小顺序第三个结点的值为4。
* 解法一：时间复杂度O(k),空间复杂度O(1)
*
* @param root
* @param k
* @return
*/
int count = 0;// 计数器 public TreeNode KthNodeRe(TreeNode root, int k) {
if (root != null) {
TreeNode node = KthNodeRe(root.left, k);
if (node != null)
return node;
count++;
if (count == k)
return root;
node = KthNodeRe(root.right, k);
if (node != null)
return node;
}
return null;
} ArrayList<TreeNode> arr = new ArrayList<TreeNode>(); /**
* 解法二：时间复杂度O(n),空间复杂度O(n)
*
* @param pRoot
* @param k
* @return
*/
public TreeNode KthNode(TreeNode pRoot, int k) {
if (pRoot == null || k <= 0)
return null;
InOder(pRoot);
return k > arr.size() ? null : arr.get(arr.size() - k);
} public void InOder(TreeNode pRoot) {
if (pRoot == null)
return;
InOder(pRoot.left);
arr.add(pRoot);
InOder(pRoot.right);
} /**
* 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
* 那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
* 那么中位数就是所有数值排序之后中间两个数的平均值
* @param num
*/
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(
new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
public void Insert(Integer num) {
if (count % 2 == 0) {
// 1.新加入的元素先入到大根堆，由大根堆筛选出堆中最大的元素
maxHeap.offer(num);
int filteredMaxNum = maxHeap.poll();
// 2.筛选后的【大根堆中的最大元素】进入小根堆
minHeap.offer(filteredMaxNum);
} else {
// 1.新加入的元素先入到小根堆，由小根堆筛选出堆中最小的元素
minHeap.offer(num);
int filteredMinNum = minHeap.poll();
// 2.筛选后的【小根堆中的最小元素】进入大根堆
maxHeap.offer(filteredMinNum);
}
count++;
} public Double GetMedian() {
if (count % 2 == 0) {
return new Double((minHeap.peek() + maxHeap.peek())) / 2;
} else {
return new Double(minHeap.peek());
}
} @Test
public void testDeserialize() {
String str = "1,2,4,#,#,5,#,#,3,#,#";
TreeNode root = Deserialize(str);
preOderTree(root);
} @Test
public void testBuildTreePre() {
String str = "1,2,4,#,#,5,#,#,3,#,#";
TreeNode root = Deserialize(str);
// preOderTree(root);
String serialize = Serialize(root);
System.out.println(serialize);
} @Test
public void testBuildTreeLevel() {
int[] a = { 1, 2, 3, 4, 5 };
TreeNode root = buildTreeLevel(a);
inOderTree(root);
} @Test
public void testBuildTreeKthNode() {
int[] a = { 4, 2, 5, 1, 3 };
TreeNode root = buildTreeLevel(a);
inOderTree(root);
}
}
最新文章
- SQL统计
- 超链接标签a样式生效，取消下划线，文字垂直（上下）居中
- 美女程序员是如何将QQ转换成题目中那串数字的--读博文《找女神要QQ号码》
- jQuery学习总结（二）
- [牛感悟系列]JAVA（1）理解JAVA垃圾回收
- Oracle EBS-SQL (SYS-17):查询一张报表在哪个职责下面.sql
- SDUT 1124-飞跃荒野（三维BFS）
- Knockout简单用法
- stock 当天盘势
- MyEclipse 修改项目字符集
- 集合、增强for、泛型
- Adobe Audition 基本使用
- pgsql 并行相关配置
- matlab运行出现“变量似乎会随着迭代次数改变而变化，请预分配内存，以提高运行速度”问题
- Spark安装部署| 运行模式
- Linux命令（一）
- T_RegionNDS表创建及值
- 跟我一起写Makefile:使用函数
- Spring 依赖注入 基于构造函数、设值函数、内部Beans、集合注入
- sparkSQL——DataFrame&Datasets