当前位置:网站首页>Construction and traversal of binary tree
Construction and traversal of binary tree
2022-04-23 10:16:00 【Popuessing's Jersey】
import java.util.ArrayList;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode root;
TreeNode(){}
TreeNode(int val){
this.val = val;
}
TreeNode(int val, TreeNode left,TreeNode right){
this.val = val;
this.right = right;
this.left = left;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
// The former sequence traversal —— recursive LC144—— Preorder traversal of two tree
ArrayList<Integer> preorderReverse(TreeNode root){
ArrayList<Integer> result = new ArrayList<>();
preOrder(root,result);
return result;
}
// Recursive parameters and return types
void preOrder(TreeNode root,ArrayList<Integer> result){
// Recursive termination condition
if (root == null){
return;
}
// Recursive single-layer logic
result.add(root.val);
preOrder(root.left,result);
preOrder(root.right,result);
}
// In the sequence traversal · recursive ·LC94_ Middle order traversal of binary trees
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
inorder(root,res);
return res;
}
void inorder(TreeNode root,ArrayList<Integer> list){
if (root == null){
return;
}
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
// After the sequence traversal · recursive ·LC145_ Postorder traversal of binary trees
public ArrayList<Integer> postorderTraversal(TreeNode root){
ArrayList <Integer> res = new ArrayList<>();
postorder(root,res);
return res;
}
void postorder(TreeNode root,ArrayList<Integer> list){
if (root == null){
return;
}
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
}
public void createTree(int [] nums){
// Create a collection to save the node of the tree
ArrayList<TreeNode> treeNodes = new ArrayList<>();
for (int tempdata:nums) {
treeNodes.add(new TreeNode(tempdata));
}
// Set the first node as the root node
root = treeNodes.get(0);
/*
* Use the method of building a complete binary tree to build
* */
for (int i = 0; i < treeNodes.size()/2; i++) {
if ((i*2+1)< treeNodes.size()){
treeNodes.get(i).setLeft(treeNodes.get(i*2+1));
}
if ((i*2+2)< treeNodes.size()){
treeNodes.get(i).setRight(treeNodes.get(i*2+2));
}
}
}
public static void main(String[] args) {
int [] nums = {1,2,3,4,5,6,7,8};
TreeNode treeNode = new TreeNode();
treeNode.createTree(nums);
ArrayList<Integer> res1 =treeNode.preorderReverse(treeNode.getRoot());
ArrayList<Integer> res2 =treeNode.inorderTraversal(treeNode.getRoot());
ArrayList<Integer> res3 =treeNode.postorderTraversal(treeNode.getRoot());
System.out.println(res1);
System.out.println(res2);
System.out.println(res3);
}
}
Output results :
[1, 2, 4, 8, 5, 3, 6, 7]
[8, 4, 2, 5, 1, 6, 3, 7]
[8, 4, 5, 2, 6, 7, 3, 1]
版权声明
本文为[Popuessing's Jersey]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231011140653.html
边栏推荐
- 997、有序数组的平方(数组)
- Using multithreading to output abc10 times in sequence
- 0704、ansible----01
- DBA common SQL statements (1) - overview information
- mysql同一个表中相同数据怎么合并
- 中职网络安全2022国赛之CVE-2019-0708漏洞利用
- LeetCode 1249. Minimum remove to make valid parents - FB high frequency question 1
- 2022 mobile crane driver test question bank simulation test platform operation
- 二叉树的构建和遍历
- SQL tuning series - SQL performance methodology
猜你喜欢
随机推荐
Detailed explanation of MapReduce calculation process
What about Jerry's stack overflow? [chapter]
2022年制冷与空调设备运行操作考试练习题及模拟考试
Jerry's users how to handle events in the simplest way [chapter]
解决方案架构师的小锦囊 - 架构图的 5 种类型
Go language practice mode - functional options pattern
Using idea to develop Spark Program
JVM——》常用参数
SQL调优系列文章之—SQL调优简介
Arm debugging (1): two methods to redirect printf to serial port in keil
Sim Api User Guide(8)
一文读懂PlatoFarm新经济模型以及生态进展
Ansible cloud computing automation command line compact version
杰理之系统事件有哪些【篇】
MapReduce压缩
59、螺旋矩阵(数组)
二叉树的构建和遍历
101. Symmetric Tree
通过流式数据集成实现数据价值(1)
Shell script interaction free