当前位置:网站首页>Summary of common algorithms of binary tree
Summary of common algorithms of binary tree
2020-11-06 01:18:00 【Clamhub's blog】
Node definition
1 |
public static class BinaryNode<T> { |
Binary tree nodes include element values and left and right child node references .
Create nodes
1 |
BinaryNode g = new BinaryNode(7); |
Form like :
1、 front 、 in 、 After the sequence traversal
In front of the binary tree 、 in 、 Before in postorder traversal 、 in 、 The root node ;
Before the order : Output the root node first , And then the left and right nodes .
Middle preface : First left , Then output the root node , To the right .
In the following order : First left and right , Then output the root node .
1 |
public static void visit(BinaryNode p) { |
1.1、 The former sequence traversal
1 |
root -> Left -> Right |
1.1.1、 Recursive implementation
1 |
public static void recursivePreOrder(BinaryNode p) { |
If the node is null, Go straight back to ;
Print out the root node first , Then recursion left subtree , Then recurs the right subtree .
Just meet : First root , And then around .
1.1.2、 Non recursive implementation
1 |
public static void iterativePreOrder(BinaryNode p) { |
Make full use of the idea of stack , First in, then out .
When the node is not empty , Putting nodes on the stack , Iterate the elements in the stack , Pop up top element , Currently the root element , After that, press the right and left child nodes on the stack respectively . In this way, the order of the child nodes is left first and then right .
1.2、 In the sequence traversal
1 |
Left -> root -> Right |
1.2.1、 Recursive implementation
1 |
public static void recursiveInOrder(BinaryNode p) { |
1.2.2、 Non recursive implementation
1 |
public static void iterativeInOrder(BinaryNode p) { |
1.3、 After the sequence traversal
1 |
Left -> Right -> root |
1.3.1、 Recursive implementation
1 |
public static void recursivePostOrder(BinaryNode p) { |
1.3.2、 Non recursive implementation
1 |
public static void iterativePostOrder(BinaryNode p) { |
2、BFS And DFS
2.1、BFS Breadth first search
1 |
1234567 |
Breadth first traversal is to read node elements by layer , We need to use the data structure of the queue .
1 |
public static void levelOrderTraversal(BinaryNode node) { |
2.2、DFS Depth-first search
1 |
1245367 |
Starting from the root node , Select a branch to read all the elements , We need to use the data structure of the stack .
1 |
public static void depthTraversal(BinaryNode node) { |
3、 The depth of the binary tree
104. The maximum depth of a binary tree
3.1、 recursive
1 |
private static int calcDepth(BinaryNode node) { |
3.2、 Depth first
maxDepth Compare the length of each branch to update , Finally get the deepest branch length .
1 |
public static int maxDepthDFS(BinaryNode node) { |
3.3、 breadth-first
Search by layer , Every step into the floor , depth +1.
1 |
public static int maxDepthBFS(BinaryNode node) { |
4、 Binary tree image
Traverse by depth or breadth , Swap the left and right subtrees of nodes .
1 |
public static void mirror(BinaryNode root) { |
5、 Symmetric binary tree
101. Symmetric binary tree
This problem is a variation of binary tree mirror image , If two binary trees are symmetric , be :
- Two root nodes have the same value
- The left subtree of each tree , Are the same as the right subtree of another tree
Recursive implementation :1
2
3
4
5
6
7
8
9
10
11public boolean isSymmetric(BinaryNode root) {
return isMirror(root, root);
}
public boolean isMirror(BinaryNode t1, BinaryNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val)
&& isMirror(t1.right, t2.left)
&& isMirror(t1.left, t2.right);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public boolean isSymmetric(BinaryNode root) {
LinkedList<BinaryNode> q = new LinkedList<>();
q.add(root);
q.add(root);
while (!q.isEmpty()) {
BinaryNode t1 = q.poll();
BinaryNode t2 = q.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
summary
The algorithm of various topics of binary tree will think of recursion in the first consciousness , But when the recursion depth is too large, there will be stack overflow , So iterations will be used to implement accordingly , Accordingly, the data structure of queue or stack is introduced .
It feels like the most important algorithm is DFS And BFS, among DFS Depth first search uses the FIFO feature of the stack , and BFS Breadth first search uses the first in first out feature of the queue .
版权声明
本文为[Clamhub's blog]所创,转载请带上原文链接,感谢
边栏推荐
- 有关PDF417条码码制的结构介绍
- Asp.Net Core learning notes: Introduction
- 阿里云Q2营收破纪录背后,云的打开方式正在重塑
- 数字城市响应相关国家政策大力发展数字孪生平台的建设
- C++和C++程序员快要被市场淘汰了
- It's so embarrassing, fans broke ten thousand, used for a year!
- Grouping operation aligned with specified datum
- xmppmini 專案詳解:一步一步從原理跟我學實用 xmpp 技術開發 4.字串解碼祕笈與訊息包
- Filecoin主网上线以来Filecoin矿机扇区密封到底是什么意思
- 嘗試從零開始構建我的商城 (二) :使用JWT保護我們的資訊保安,完善Swagger配置
猜你喜欢
Grouping operation aligned with specified datum
制造和新的自动化技术是什么?
Troubleshooting and summary of JVM Metaspace memory overflow
数字城市响应相关国家政策大力发展数字孪生平台的建设
DevOps是什么
Computer TCP / IP interview 10 even asked, how many can you withstand?
How long does it take you to work out an object-oriented programming interview question from Ali school?
Subordination judgment in structured data
至联云分享:IPFS/Filecoin值不值得投资?
DTU连接经常遇到的问题有哪些
随机推荐
Swagger 3.0 天天刷屏,真的香嗎?
你的财务报告该换个高级的套路了——财务分析驾驶舱
It's so embarrassing, fans broke ten thousand, used for a year!
Examples of unconventional aggregation
做外包真的很难,身为外包的我也无奈叹息。
EOS创始人BM: UE,UBI,URI有什么区别?
PLC模拟量输入和数字量输入是什么
Face to face Manual Chapter 16: explanation and implementation of fair lock of code peasant association lock and reentrantlock
条码生成软件如何隐藏部分条码文字
Calculation script for time series data
Filecoin的经济模型与未来价值是如何支撑FIL币价格破千的
H5 makes its own video player (JS Part 2)
怎么理解Python迭代器与生成器?
Didi elasticsearch cluster cross version upgrade and platform reconfiguration
带你学习ES5中新增的方法
In order to save money, I learned PHP in one day!
After brushing leetcode's linked list topic, I found a secret!
CCR炒币机器人:“比特币”数字货币的大佬,你不得不了解的知识
Flink的DataSource三部曲之二:内置connector
Network programming NiO: Bio and NiO