# JAVA数据结构刷题 -- 力扣二叉树

## 🍎🍎一、实现二叉树的基本操作

package com.practice;
import java.util.Queue;
public class BinaryTree {
static class TreeNode {
public char val;
public TreeNode left;//左孩子的引用
public TreeNode right;//右孩子的引用
public TreeNode(char val) {
this.val = val;
}
}
/**
* 创建一棵二叉树 返回这棵树的根节点
*
* @return
*/
public TreeNode createTree() {
TreeNode node1 = new TreeNode('A');
TreeNode node2 = new TreeNode('B');
TreeNode node3 = new TreeNode('C');
TreeNode node4 = new TreeNode('D');
TreeNode node5 = new TreeNode('E');
TreeNode node6 = new TreeNode('F');
TreeNode node7 = new TreeNode('G');
node1.left = node2;
node1.right = node3;
node2.left = node4;
node3.left = node5;
node3.right = node6;
node4.right = node7;
return node1;
}
// 前序遍历
public void preOrder(TreeNode root) {
if (root == null) return;
System.out.println(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
System.out.println(root.val + " ");
inOrder(root.right);
}
// 后序遍历
void postOrder(TreeNode root) {
if (root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.println(root.val + " ");
}
public int nodeSize = 0;
/**
* 获取树中节点的个数：遍历思路
*/
public int size(TreeNode root) {
if (root == null) {
return 0;
}
nodeSize++;
size(root.left);
size(root.right);
return nodeSize;
}
/**
* 获取节点的个数：子问题的思路
*
* @param root
* @return
*/
int size2(TreeNode root) {
if (root == null) {
return 0;
}
return size2(root.left) + size2(root.right) + 1;
}
/*
获取叶子节点的个数：遍历思路
*/
public static int leafSize = 0;
int getLeafNodeCount1(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
leafSize++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
return leafSize;
}
/*
获取叶子节点的个数：子问题
*/
int getLeafNodeCount2(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
}
/*
获取第K层节点的个数
*/
int getKLevelNodeCount(TreeNode root, int k) {
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
}
/*
获取二叉树的高度
时间复杂度：O(N)
*/
int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
return ((leftH>rightH)?leftH:rightH) + 1;
}
// 检测值为value的元素是否存在
TreeNode find(TreeNode root, char val) {
if(root == null) {
return null;
}
if(val == root.val){
return root;
}
TreeNode leftR = find(root.left,val);
if(leftR != null) {
return leftR;
}
TreeNode rightR = find(root.right,val);
if(rightR != null) {
return rightR;
}
return null;
}
//层序遍历
void levelOrder(TreeNode root) {
if(root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
System.out.print(top.val + " ");
if(top.left != null) {
queue.offer(top.left);
}
if(top.right != null) {
queue.offer(top.right);
}
}
}
// 判断一棵树是不是完全二叉树
boolean isCompleteTree(TreeNode root) {
if(root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur != null) {
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur != null){
return false;
}
}
return true;
}
}

## ✨✨二、平衡二叉树的判断

class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
return getHeight2(root) >= 0;
}
int getHeight2(TreeNode root) {
if (root == null) {
return 0;
}
int leftH = getHeight2(root.left);
int rightH = getHeight2(root.right);
if(leftH >= 0 && rightH >= 0 && Math.abs(leftH - rightH) <= 1) {
return Math.max(leftH,rightH) + 1;
} else {
return -1;
}
}
}

## 🍎🍎三、二叉树的构建及遍历

import java.util.Scanner;
class TreeNode {
public char value;
public TreeNode left;
public TreeNode right;
public TreeNode(char value) {
this.value = value;
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
String str = in.nextLine();
TreeNode root = createTree(str);
inOrder(root);
}
}
public static int i = 0;
public static TreeNode createTree(String str) {

TreeNode root = null;
if(str.charAt(i) != '#'){
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);
root.right = createTree(str);
}else {
i++;
}
return root;
}
public static void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
System.out.print(root.value + " ");
inOrder(root.right);
}
}

## 🍎🍎四、另一棵树的子树

class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null) {
return false;
}
if(isSameTree(root,subRoot)) {
return true;
}
if(isSubtree(root.left,subRoot)) {
return true;
}
if(isSubtree(root.right,subRoot)) {
return true;
}
return false;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q != null || p != null && q == null) {
return false;
}
if (p == null && q == null) {
return true;
}
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}
}

## ✨✨五、对称二叉树

class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode leftTree ,TreeNode righjtTree) {
if(leftTree == null && righjtTree != null || leftTree != null && righjtTree == null ) {
return false;
}
if(leftTree == null && righjtTree == null) {
return true;
}
if(leftTree.val != righjtTree.val) {
return false;
}
return isSymmetricChild(leftTree.left,righjtTree.right) && isSymmetricChild(leftTree.right,righjtTree.left);
}
}

## 🍎🍎六、检查两棵树是否相同

class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null || p != null && q == null){
return false;
}
if(p == null && q == null){
return true;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left)
&&isSameTree(p.right,q.right);
}
}

## ✨✨七、反转二叉树

class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}

|
4天前
|

9 2
|
20小时前
|

【算法】重建二叉树并进行后序遍历的Java实现
【算法】重建二叉树并进行后序遍历的Java实现
11 5
|
21小时前
|

9 3
|
1天前
|

【二叉树】数据结构——BST二叉树基本概念及算法设计（插入、删除、遍历操作）
【二叉树】数据结构——BST二叉树基本概念及算法设计（插入、删除、遍历操作）
7 0
|
1天前
|

【树】数据结构——树和二叉树的概念&笔记
【树】数据结构——树和二叉树的概念&笔记
6 1
|
3天前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
12 2
|
3天前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
18 2
|
3天前
|

6 1
|
3天前
|

5 0
|
4天前
|

Java高并发实战：利用线程池和Redis实现高效数据入库
Java高并发实战：利用线程池和Redis实现高效数据入库
18 0