在 Java 中能够通过上面这种形式定义一个二叉树的类：
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
}
上面介绍一些操作二叉树的根本办法：
文章目录
1. 构建二叉树
2. 深度优先遍历
3. 层序遍历
4. 如何判断两个二叉树雷同
5. 如何判断一个二叉树是否对称
1. 构建二叉树
/**
* 构建二叉树
* @param inputList 输出序列
* @return node 返回根节点
*/
public static TreeNode creatBinaryTree(LinkedList<Integer> inputList){
TreeNode node = null;
if(inputList == null || inputList.isEmpty()){
return null;
}
Integer data = 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<Integer> inputList = new LinkedList<Integer>(
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<TreeNode> queue = new LinkedList<TreeNode>();
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
/ \
2 2
/ \ / \
3 4 4 3
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(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);
}
}