二叉树的基本操作 java

在Java中可以通过下面这种方式定义一个二叉树的类：
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = https://www.it610.com/article/data;
}
下面介绍一些操作二叉树的基本方法：
文章目录
1.构建二叉树
2.深度优先遍历
3.层序遍历
4.如何判断两个二叉树相同
5.如何判断一个二叉树是否对称
1.构建二叉树
/**
* 构建二叉树
* @param inputList 输入序列
* @return node 返回根节点
【二叉树的基本操作】*/
public static TreeNode creatBinaryTree(LinkedList inputList){
TreeNode node = null;
if(inputList == null || inputList.isEmpty()){
return null;
}
Integer data = https://www.it610.com/article/inputList.removeFirst(); //去除并返回LinkedList中的第一个元素
if (data != null){
node = new TreeNode(data);
node.left = creatBinaryTree(inputList);
node.right = creatBinaryTree(inputList);
}
return node;
}
main函数：
public static void main(String[] args) {
LinkedList inputList = new LinkedList(
Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4})
);
TreeNode treeNode = creatBinaryTree(inputList);
}
2.深度优先遍历
深度优先遍历分为前序遍历，中序遍历，后序遍历。主要采用递归的思路
/**
* 前序遍历
* @param node 二叉树根节点
*/
public static void preOrderTraveral(TreeNode node){
if (node == null){
return;
}
System.out.println(node.data);
preOrderTraveral(node.left);
preOrderTraveral(node.right);
}
/**
* 中序遍历
* @param node 二叉树根节点
*/
public static void inOrderTraveral(TreeNode node){
if (node == null){return; }
inOrderTraveral(node.left);
System.out.println(node.data);
inOrderTraveral(node.right);
}
/**
* 后序遍历
* @param node 二叉树根节点
*/
public static void postOrderTraveral(TreeNode node){
if(node == null){
return;
}
postOrderTraveral(node.left);
postOrderTraveral(node.right);
System.out.println(node.data);
}
3.层序遍历
/**

@author 结构化思维wz
二叉树的层序遍历

*/
public class LevelOrder {
public static Queue levelOrderTraversal(TreeNode root){
Queue queue = new LinkedList();
queue.offer(root);
while(! queue.isEmpty()){
TreeNode node = queue.poll();
System.out.println(node.data);
if(node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
}
return queue;
}
}
4.如何判断两个二叉树相同
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){return true; } //都为空必然相同
if(p == null || q == null){return false; } //一个空一个非空肯定是false；
if(p.val != q.val){
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right , q.right);
}
}
5.如何判断一个二叉树是否对称
给定一个二叉树，检查它是否是镜像对称的。java培训
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
22
/ \ / \
34 43
class Solution {
public boolean isSymmetric(TreeNode root) {
returncheck(root.left,root.right);
}
public boolean check(TreeNode p, TreeNode q){
if(p ==null && q ==null){return true; }
if(p == null || q == null){return false; }
return p.val == q.val && check(p.left , q.right) &&check(p.right ,q.left);
}
}