常见算法总结 - 二叉树篇
2020-05-04 16:03:57来源:博客园 阅读 ()
常见算法总结 - 二叉树篇
本文总结了常见高频的关于二叉树的算法考察。
1.计算一个给定二叉树的叶子节点数目。
可以采用递归的方式进行累加
public static int calculateTreeNodeNumber(TreeNode treeNode) {
if (treeNode == null) {
return 0;
}
return calculateTreeNodeNumber(treeNode.left) + calculateTreeNodeNumber(treeNode.right) + 1;
}
2.计算二叉树的深度。
跟上题一样采用递归的方式,但需返回左右子树中较深的深度。
public static int getTreeDepth(TreeNode tree) {
if (tree == null) {
return 0;
}
int left = getTreeDepth(tree.left);
int right = getTreeDepth(tree.right);
return left >= right ? left + 1 : right + 1;
}
3.如何打印二叉树每层的节点。
借助一个队列,先把根节点入队,每打印一个节点的值时,也就是打印队列头的节点时,都会把它的的左右孩子入队,并且把该节点出队。直到队列为空。
public static void printByLevel(TreeNode tree) {
if (tree == null) {
return;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(tree);
while (!queue.isEmpty()) {
TreeNode pop = queue.pop();
System.out.println(pop.val);
if (pop.left != null) {
queue.add(pop.left);
}
if (pop.right != null) {
queue.add(pop.right);
}
}
}
4.二叉树的Z型遍历。
借助两个队列,一个正序打印,一个逆序打印。
public static void printByZ(TreeNode tree) {
if (tree == null) {
return;
}
List<TreeNode> orderQueue = new ArrayList<>();
List<TreeNode> disorderQueue = new ArrayList<>();
orderQueue.add(tree);
while (!orderQueue.isEmpty()|| !disorderQueue.isEmpty()) {
if (!orderQueue.isEmpty()) {
for (int i = 0; i < orderQueue.size(); i++) {
TreeNode leaf = orderQueue.get(i);
if (leaf.left != null) {
disorderQueue.add(leaf.left);
}
if (leaf.right != null) {
disorderQueue.add(leaf.right);
}
}
for (TreeNode node : orderQueue) {
System.out.println(node.val);
}
orderQueue.clear();
}
if (!disorderQueue.isEmpty()) {
for (int i = 0; i < disorderQueue.size(); i++) {
TreeNode leaf = disorderQueue.get(i);
if (leaf.left != null) {
orderQueue.add(leaf.left);
}
if (leaf.right != null) {
orderQueue.add(leaf.right);
}
}
for (int i = disorderQueue.size()-1; i >=0 ; i--) {
TreeNode leaf = disorderQueue.get(i);
System.out.println(leaf.val);
}
disorderQueue.clear();
}
}
}
5.一个已经构建好的TreeSet,怎么完成倒排序。
递归更换左右子树即可
public static void reverse(TreeNode tree) {
if (tree.left == null && tree.right == null) {
return;
}
TreeNode tmp = tree.right;
tree.right = tree.left;
tree.left = tmp;
reverse(tree.left);
reverse(tree.right);
}
6.二叉树的前序遍历。
前序递归
public static void preOrderRecursion(TreeNode tree) {
if (tree != null) {
System.out.print(tree.val + "->");
preOrderRecursion(tree.left);
preOrderRecursion(tree.right);
}
}
前序非递归
public static void preOrderNonRecursion(TreeNode tree) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = tree;
while (node != null || !stack.empty()) {
if (node != null) {
System.out.print(node.val + "->");
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
node = tem.right;
}
}
}
7.二叉树的中序遍历。
中序递归
public static void middleOrderRecursion(TreeNode tree) {
if (tree != null) {
middleOrderRecursion(tree.left);
System.out.print(tree.val + "->");
middleOrderRecursion(tree.right);
}
}
中序非递归
public static void middleOrderNonRecursion(TreeNode tree) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = tree;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
System.out.print(tem.val + "->");
node = tem.right;
}
}
}
8.二叉树的后序遍历。
后序递归
public static void postOrderTraverseRecursion(TreeNode root) {
if (root != null) {
postOrderTraverseRecursion(root.left);
postOrderTraverseRecursion(root.right);
System.out.print(root.val + "->");
}
}
后序非递归
public static void postOrderTraverseNonRecursion1(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<TreeNode> output = new LinkedList<>();
if (root == null) {
return;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
output.addFirst(node);
if (node.left != null) {
stack.add(node.left);
}
if (node.right != null) {
stack.add(node.right);
}
}
for (TreeNode node : output) {
System.out.print(node.val + "->");
}
}
笔者个人总结,如有错误之处望不吝指出。
本文转自我的个人博客:《CoderV的进阶笔记》
欢迎加入Java后端架构技术讨论群:1398880
我的公众号:CoderV的进阶笔记,记录技术心得
原文链接:https://www.cnblogs.com/valarchie/p/12825467.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:XML学习笔记
- DES/3DES/AES 三种对称加密算法实现 2020-06-11
- JVM常见面试题解析 2020-06-11
- 总结一些 Java 相关笔试、面试题,万一用上了呢 (=_=) -- 基 2020-06-08
- 最新四面京东拿offer回来分享面试经验总结(技术三面+HR面) 2020-06-04
- 国外大佬总结的 10 个 Java 编程技巧! 2020-06-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash