ACM模式下构建二叉树来实现各个核心代码 （java含注释）

前言

acm模式下需要构建二叉树以及定义二叉树的定义性质
经常写leetcode或者核心代码的时候，会不知所措
以下主要讲解如何在acm模式下 完整书写二叉树代码

1. 知识点

对于二叉树的性质，可看我以下文章：

• 二叉树基本性质定理：【数据结构】树和二叉树详细分析（全）
• b树以及b+树区分： 【数据结构】B树和B+树的笔记详细诠释

基本的核心代码可看如下文章：
【代码随想录】二叉树和二叉搜索树的专栏（java版本含注释）

2. 定义及构建二叉树

难点在于如何定义以及构建生成二叉树，之后调用核心代码输出结果

定义二叉树：

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

构建二叉树：

public static TreeNode construct(int[] arr){
    List<TreeNode> list = new ArrayList<>();
    TreeNode root = null;
    int n = arr.length;
    for(int i = 0;i < n;i++){
        TreeNode node = null;
        // 对应数组的-1节点为null，如果不定义int类型数组，则可使用Object类型来判定null类型
        if(arr[i] != -1){
            node = new TreeNode(arr[i]);
        }
        list.add(node);
        // 区分根节点，将其定义为root
        if(i == 0)root = node;
    }
	
	// 通过二叉树的性质来生成，结尾节点是 i*2 + 1
    for(int i = 0;i * 2 + 1 < n;i++){
        TreeNode node = list.get(i);
        if(node != null){
        	// 左节点指向
            node.left = list.get(i * 2 + 1);
            // 再次判断下
            if(i * 2 + 2 < n){
            	// 右节点指向
                node.right = list.get(i * 2 + 2);
            }
        }
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3. 完整代码

假设求二叉树的右视图，也就是求树的所有右节点
具体核心代码如下：（通过层次遍历的结构）

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null)return list;

    LinkedList<TreeNode> que = new LinkedList<>();
    que.offer(root);
    while(!que.isEmpty()){
        int n = que.size();
        for(int i = 0;i < n;i++){
            TreeNode node = que.poll();
            if(i == n - 1)list.add(node.val);
            if(node.left != null) que.offer(node.left);
            if(node.right != null) que.offer(node.right);
        }
    }
    return list;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

完整代码如下：

import java.util.*;

class test3 {
	// acm的测试代码
    public static void main(String[] args) {
    	// 此处如果是Scanner的获取，可通过Scanner进行输入对应数组
        int[] arrs = {1,2,3,-1,5,-1,4};
        TreeNode root = construct(arrs);
        List<Integer> objects = rightSideView(root);
        for(int i = 0 ;i < objects.size();i++){
            System.out.println(objects.get(i));
        }

    }
	
	//定义二叉树性质 
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

	// 构建生成二叉树
    public static TreeNode construct(int[] arr){
        List<TreeNode> list = new ArrayList<>();
        TreeNode root = null;
        int n = arr.length;
        for(int i = 0;i < n;i++){
            TreeNode node = null;
            if(arr[i] != -1){
                node = new TreeNode(arr[i]);
            }
            list.add(node);
            if(i == 0)root = node;
        }

        for(int i = 0;i * 2 + 1 < n;i++){
            TreeNode node = list.get(i);
            if(node != null){
                node.left = list.get(i * 2 + 1);
                if(i * 2 + 2 < n){
                    node.right = list.get(i * 2 + 2);
                }
            }
        }
        return root;
    }
	
	// 核心代码
    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)return list;

        LinkedList<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int n = que.size();
            for(int i = 0;i < n;i++){
                TreeNode node = que.poll();
                if(i == n - 1)list.add(node.val);
                if(node.left != null) que.offer(node.left);
                if(node.right != null) que.offer(node.right);
            }
        }
        return list;

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

如果使用Object定义数组类型：
对应修改上面的代码如下：

class test3 {
    public static void main(String[] args) {
		
		// 只有Object才可为null
        Object[] arrs = {1,2,3,null,5,null,4};
        TreeNode root = construct(arrs);
        List<Object> objects = rightSideView(root);
        for(int i = 0 ;i < objects.size();i++){
            System.out.println(objects.get(i));
        }


    }

	// 数值类型为Object
    public static class TreeNode{
        Object val;
        TreeNode left;
        TreeNode right;
        public TreeNode(Object val){
            this.val = val;
        }

        public TreeNode(Object val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static TreeNode construct(Object[] arr){
        List<TreeNode> list = new ArrayList<>();
        TreeNode root = null;
        int n = arr.length;
        for(int i = 0;i < n;i++){
            TreeNode node = null;
            if(arr[i] != null){
                node = new TreeNode(arr[i]);
            }
            list.add(node);
            if(i == 0)root = node;
        }
		
		// 对应判断应该修改为null
        for(int i = 0;i * 2 + 1 < n;i++){
            TreeNode node = list.get(i);
            if(node != null){
                node.left = list.get(i * 2 + 1);
                if(i * 2 + 2 < n){
                    node.right = list.get(i * 2 + 2);
                }
            }
        }
        return root;
    }

	// 区别在于Object
    public static List<Object> rightSideView(TreeNode root) {
        List<Object> list = new ArrayList<>();
        if(root == null)return list;

        LinkedList<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int n = que.size();
            for(int i = 0;i < n;i++){
                TreeNode node = que.poll();
                if(i == n - 1)list.add(node.val);
                if(node.left != null) que.offer(node.left);
                if(node.right != null) que.offer(node.right);
            }
        }
        return list;

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

---

不同核心代码，测试函数的输出就不大一样
如求二叉树的最小高度
完整代码如下：

import java.util.*;

class test3 {
    public static void main(String[] args) {
        int[] arrs = {1,2,3,-1,5,-1,4};
        TreeNode root = construct(arrs);
		
		// 测试代码
        int i = minDepth(root);
        System.out.println(i);

    }
	// 定义二叉树 如上
	// 构建二叉树 如上
	
	// 核心代码
    public static int minDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null) return minDepth(root.right) + 1;
        else if (root.right == null) return minDepth(root.left) + 1;
        else return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

如果想自我捕捉输入
可查看这篇文章：java之Sacnner类常用函数next()、nextLine()、hasNext()和hasNextLine()详解