@[TOC]
摘要
- 问题1：求二叉树的最大深度
- 问题2：求二叉树的最小深度
- 问题3：求二叉树中节点的个数
- 问题4：求二叉树中叶子节点的个数
- 问题5：求二叉树中第k层节点的个数（不是求第k层叶子节点个数）
- 问题6：判断两棵树是否相同
- 问题7：给定一个二叉树，检查它是否是镜像对称的。
- 问题8：（递归）二叉树的前序遍历
- 问题9：（递归）二叉树的中序遍历
- 问题10：（递归）二叉树的后序遍历
代码
Node节点
import lombok.Data;
/**
* 二叉树数据结构
* @author: liudz
* @date: 2021/4/8
*/
@Data
public class Node {
int val;//节点数据
Node left;//左子节点的引用
Node right;//右子节点的引用
public Node() {};
public Node(int val) {
this.val = val;
left = null;
right = null;
}
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}
main函数
public static void main(String[] args){
Node p1 = new Node(1, new Node(2), new Node());
Node q1 = new Node(1, new Node(), new Node(2));
/* a1:↓ a2：↓ a3：↓
1 1 1
/ \ / \
2 3 2 3
/ \
4 5
/
6
*/
Node a1 = new Node(1, new Node(2, new Node(4), new Node(5, new Node(6), null)), new Node(3));
Node a2 = new Node(1, null, null);
Node a3 = new Node(1, new Node(2, null, null), new Node(3, null, null));
//问题10：（递归）二叉树的后序遍历
// postOrderRe(a1).stream().forEach(item -> System.out.print(item + " "));
//问题9：（递归）二叉树的中序遍历
// midOrderRe(a1).stream().forEach(item -> System.out.print(item + " "));
//问题8：（递归）二叉树的前序遍历
// preOrderReverse(a1).stream().forEach(item -> System.out.print(item + " "));
//问题5：求二叉树中第k层节点的个数（不是求第k层叶子节点个数）
// System.out.println("numsOfkLevelTreeNode:" + numsOfkLevelTreeNode(a1, 3));
//问题4：求二叉树中叶子节点的个数
// System.out.println("numsOfNoChildNode:" + numsOfNoChildNode(a1));
//问题3：求二叉树中节点的个数
// System.out.println("numOfTreeNode:" + numOfTreeNode(a1));
//问题2：求二叉树的最小深度
// System.out.println("mintreeDepth:" + mintreeDepth(a1));
//问题1：求二叉树的最大深度
// System.out.println("maxtreeDepth:" + maxtreeDepth(a1));
//问题7：给定一个二叉树，检查它是否是镜像对称的。
// System.out.println(isSymmetric(p1, q1));
//问题6：判断两棵树是否相同
// System.out.println(isSameTree(p1, q1));
}
问题1：递归——求二叉树的最大深度
/**
* 问题1：递归——求二叉树的最大深度
* @param node node
* @Author liudz
* @Date 2021/6/29
* @return
*/
public static int maxtreeDepth(Node node){
if (node == null) {
return 0;
}
return Math.max(maxtreeDepth(node.getLeft()), maxtreeDepth(node.getRight())) + 1;
}
问题2：求二叉树的最小深度
/**
* 问题2：求二叉树的最小深度
* @param node node
* @Author liudz
* @Date 2021/6/29
* @return
*/
public static int mintreeDepth(Node node){
if (node == null) {
return 0;
}
return Math.min(mintreeDepth(node.getLeft()), mintreeDepth(node.getRight())) + 1;
}
问题3：求二叉树中节点的个数
/**
* 问题3：求二叉树中节点的个数
* @param node node
* @Author liudz
* @Date 2021/6/29
* @return
*/
public static int numOfTreeNode(Node node){
if (node == null) {
return 0;
}
return numOfTreeNode(node.getLeft()) + numOfTreeNode(node.getRight()) + 1;
}
问题4：求二叉树中叶子节点的个数
/**
* 问题4：求二叉树中叶子节点的个数
* @param node node
* @Author liudz
* @Date 2021/6/29
* @return
*/
public static int numsOfNoChildNode(Node node){
if (node == null) {
return 0;
}
if (node.getLeft() == null && node.getRight() == null) {
return 1;
}
return numsOfNoChildNode(node.getLeft()) + numsOfNoChildNode(node.getRight());
}
问题5：求二叉树中第k层节点的个数,不是求第k层叶子节点个数
/**
* 问题5：求二叉树中第k层节点的个数,不是求第k层叶子节点个数
* @param node node
* @Author liudz
* @Date 2021/6/29
* @return
*/
public static int numsOfkLevelTreeNode(Node node, int level){
if (node == null || level <= 0) {
return 0;
}
if (node != null && level == 1) {
return 1;
}
return numsOfkLevelTreeNode(node.getLeft(), level-1) + numsOfkLevelTreeNode(node.getRight(), level-1);
}
问题6：判断两棵树是否相同
/**
* 问题6：判断两棵树是否相同
* 思路：方法一：深度优先搜索
* 如果两个二叉树都为空，则两个二叉树相同。
* 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
* 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，
* 若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。
* 这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。
* @param p p
* @param q q
* @author liudz
* @date 2021/4/21
* @return 执行结果
**/
public static boolean isSameTree(Node p, Node q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
} else if (p.getVal() != q.getVal()) {
return false;
} else {
return isSameTree(p.getLeft(), q.getLeft()) && isSameTree(p.getRight(), q.getRight());
}
}
问题7：给定一个二叉树，检查它是否是镜像对称的。
/**
* 问题7：给定一个二叉树，检查它是否是镜像对称的。
* 思路：（类似判断两棵树是否相同）
* 如果两个二叉树都为空，则两个二叉树相同。
* 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
* 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，
* 若相同，再分别判断一棵树的左子树和另一棵树的右子树是否相同
* @author liudz
* @date 2021/4/21
* @return 执行结果
**/
public static boolean isSymmetric(Node p, Node q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
}else if (p.getVal() != q.getVal()) {
return false;
}
return isSymmetric(p.getLeft(), q.getRight()) && isSymmetric(p.getRight(), q.getLeft());
}
问题8：（递归）二叉树的前序遍历
/**
* 问题8：（递归）二叉树的前序遍历
* 问题：为啥分2个方法而不是写一个方法？
* 答案：因为写一起每次ArrayList都会重新初始化，导致结果不对
* 思路：封装递归方法
* 1）根节点值添加list + 2）递归左节点 3）递归右节点
* @param node node
* @Author liudz
* @Date 2021/6/29
* @return
*/
public static List preOrderReverse(Node node){
List list = new ArrayList();
preOrder(node, list);
return list;
}
public static void preOrder(Node node, List list) {
if (node == null) {
return;
}
list.add(node.getVal());
preOrder(node.getLeft(), list);
preOrder(node.getRight(), list);
}
问题9：（递归）二叉树的中序遍历
/**
* 问题9：（递归）二叉树的中序遍历
* 问题：为啥分2个方法而不是写一个方法？
* 答案：因为写一起每次ArrayList都会重新初始化，导致结果不对
* @param node node
* @Author liudz
* @Date 2021/6/29
* @return
*/
public static List midOrderRe(Node node){
ArrayList list = new ArrayList();
midOrder(node, list);
return list;
}
public static void midOrder(Node node, List list) {
if (node == null) {
return;
}
midOrder(node.getLeft(), list);
list.add(node.getVal());
midOrder(node.getRight(), list);
}
问题10：（递归）二叉树的后序遍历
/**
* 问题10：（递归）二叉树的后序遍历
* 问题：为啥分2个方法而不是写一个方法？
* 答案：因为写一起每次ArrayList都会重新初始化，导致结果不对
* @param node node
* @Author liudz
* @Date 2021/6/29
* @return
*/
public static List postOrderRe(Node node){
ArrayList list = new ArrayList();
postOrder(node, list);
return list;
}
public static void postOrder(Node node, List list) {
if (node == null) {
return;
}
postOrder(node.getLeft(), list);
postOrder(node.getRight(), list);
list.add(node.getVal());
}
