二叉树最大深度(高度)/结点个数 / 叶子结点个数 / 第k层结点个数的求解_一颗共有5个节点的二叉树,其高度最大是多少

一、二叉树最大深度(高度)

//求二叉树最大深度/高度(DFS)
	public int maxDepth1(Node root) {
		if(root==null) {//空树高度为0
			return 0;
		}
		int leftDepth=maxDepth1(root.left);//递归计算左子树高度
		int rightDepth=maxDepth1(root.right);//递归计算右子树高度
		return Math.max(leftDepth, rightDepth)+1;//取出左右子树最大值再加上根结点高度为1
	}

//求二叉树最大深度/高度(BFS)
	public int maxDepth2(Node root) {
		if(root==null) {//空树高度为0
			return 0;
		}
		Queue<Node> queue=new LinkedList<>();
		queue.offer(root);//将根结点入队列
		int res=0;//保存二叉树的高度
		while(!queue.isEmpty()) {//遍历每层
			int size=queue.size();//当前层的结点数量
			while(size>0) {
				Node temp=queue.poll();
				if(temp.left!=null) {//当前结点左节点存在入队列
					queue.offer(temp.left);
				}
				if(temp.right!=null) {//当前结点右节点存在入队列
					queue.offer(temp.right);
				}
				size--;
			}
			res++;//每遍历完一层，将层数加一
		}
		return res;
	}
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

二、二叉树结点个数

//求二叉树的结点数(方法一)
	public int nodeCount1(Node root) {
		if(root==null) {
			return 0;
		}
		return nodeCount1(root.left)+nodeCount1(root.right)+1;
	}
	
//求二叉树的结点数(方法二)
	public static int count2 = 0;// 记录结点个数
	public int nodeCount2(Node root) {
		//int res = 0;// 记录结点个数
		if (root == null) {
			return 0;
		}
		count2++;//在遍历时所有的结点都会访问到,每访问一个结点就将count2加一
		nodeCount2(root.left);
		nodeCount2(root.right);
		return count2;
	}
	
// 求二叉树的结点数(方法三)
	public int nodeCount3(Node root) {
		int res = 0;// 记录结点的个数
		if (root == null) {// 空树直接返回0
			return 0;
		}
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node temp = stack.pop();
			res++;// 在遍历时所有的结点都会访问到,每访问一个结点就将res加一
			if (temp.left != null) {
				stack.push(temp.left);
			}
			if (temp.right != null) {
				stack.push(temp.right);
			}
		}
		return res;
	}
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

三、二叉树叶子结点个数

//求二叉树的叶子数(方法一)
	public int leafCount1(Node root){
		if(root==null) {//空树直接返回0
			return 0;
		}
		if(root.left==null&&root.right==null) {//没有左右子树即为叶子结点
			return 1;
		}
		return leafCount1(root.left)+leafCount1(root.right);
	}
	
//求二叉树的叶子数(方法二)
	public static int count1 = 0;// 记录叶子结点的个数(该count1定义必须放在函数体外，否则每次遍历时重新进行函数体时有=又重新将count1置为零，下面的count2同理)
	public int leafCount2(Node root) {
		// int res=0;//记录叶子结点的个数
		if (root == null) {// 空树直接返回0
			return 0;
		}
		if (root.left == null && root.right == null) {// 没有左右子树即为叶子结点将count1加一
			count1++;
		} else {// 否则的话就继续遍历,继续找左右孩子均为空的结点
			leafCount2(root.left);
			leafCount2(root.right);
		}
		return count1;
	}
	
//求二叉树的叶子数(方法三)
	public int leafCount3(Node root) {
		int res=0;//记录叶子结点的个数
		if (root == null) {//空树直接返回0
			return 0;
		}
		Stack<Node> stack=new Stack<>();
		stack.push(root);
		while(!stack.isEmpty()) {
			Node temp=stack.pop();
			if (temp.left == null && temp.right == null) {//没有左右子树即为叶子结点将res加一
				res++;
			}
			if(temp.left!=null) {
				stack.push(temp.left);
			}
			if(temp.right!=null) {
				stack.push(temp.right);
			}
		}
		return res;
	}
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

四、二叉树第k层结点个数

//求第k层结点个数
	public int kLevelCount(Node root,int k) {
		if(root==null) {//空树直接返回0
			return 0;
		}
		if(k==1) {//k==1即求根节点的个数，直接返回1
			return 1;
		}
		return kLevelCount(root.left,k-1)+kLevelCount(root.right,k-1);//k层节点的个数=根节点左子树的k-1层节点个数+根节点右子树的k-1层节点个数
		
	}
1
2
3
4
5
6
7
8
9
10
11

五、完整代码实现

package fighting;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
	
	public Node BuildTree() {//构造二叉树
		Node A=new Node('A');
		Node B=new Node('B');
        Node C=new Node('C');
        Node D=new Node('D');
        Node E=new Node('E');
        Node F=new Node('F');
        Node G=new Node('G');
        Node H=new Node('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
	}
	
	//求二叉树最大深度/高度(DFS)
	public int maxDepth1(Node root) {
		if(root==null) {//空树高度为0
			return 0;
		}
		int leftDepth=maxDepth1(root.left);//递归计算左子树高度
		int rightDepth=maxDepth1(root.right);//递归计算右子树高度
		return Math.max(leftDepth, rightDepth)+1;//取出左右子树最大值再加上根结点高度为1
	}

	//求二叉树最大深度/高度(BFS)
	public int maxDepth2(Node root) {
		if(root==null) {//空树高度为0
			return 0;
		}
		Queue<Node> queue=new LinkedList<>();
		queue.offer(root);//将根结点入队列
		int res=0;//保存二叉树的高度
		while(!queue.isEmpty()) {//遍历每层
			int size=queue.size();//当前层的结点数量
			while(size>0) {
				Node temp=queue.poll();
				if(temp.left!=null) {//当前结点左节点存在入队列
					queue.offer(temp.left);
				}
				if(temp.right!=null) {//当前结点右节点存在入队列
					queue.offer(temp.right);
				}
				size--;
			}
			res++;//每遍历完一层，将层数加一
		}
		return res;
	}
	
	//求二叉树的叶子数(方法一)
	public int leafCount1(Node root){
		if(root==null) {//空树直接返回0
			return 0;
		}
		if(root.left==null&&root.right==null) {//没有左右子树即为叶子结点
			return 1;
		}
		return leafCount1(root.left)+leafCount1(root.right);
	}
	
	//求二叉树的叶子数(方法二)
	public static int count1 = 0;// 记录叶子结点的个数(该count1定义必须放在函数体外，否则每次遍历时重新进行函数体时有=又重新将count1置为零，下面的count2同理)
	public int leafCount2(Node root) {
		// int res=0;//记录叶子结点的个数
		if (root == null) {// 空树直接返回0
			return 0;
		}
		if (root.left == null && root.right == null) {// 没有左右子树即为叶子结点将count1加一
			count1++;
		} else {// 否则的话就继续遍历,继续找左右孩子均为空的结点
			leafCount2(root.left);
			leafCount2(root.right);
		}
		return count1;
	}
	
	//求二叉树的叶子数(方法三)
	public int leafCount3(Node root) {
		int res=0;//记录叶子结点的个数
		if (root == null) {//空树直接返回0
			return 0;
		}
		Stack<Node> stack=new Stack<>();
		stack.push(root);
		while(!stack.isEmpty()) {
			Node temp=stack.pop();
			if (temp.left == null && temp.right == null) {//没有左右子树即为叶子结点将res加一
				res++;
			}
			if(temp.left!=null) {
				stack.push(temp.left);
			}
			if(temp.right!=null) {
				stack.push(temp.right);
			}
		}
		return res;
	}
	
	
	//求二叉树的结点数(方法一)
	public int nodeCount1(Node root) {
		if(root==null) {
			return 0;
		}
		return nodeCount1(root.left)+nodeCount1(root.right)+1;
	}
	
	//求二叉树的结点数(方法二)
	public static int count2 = 0;// 记录结点个数
	public int nodeCount2(Node root) {
		//int res = 0;// 记录结点个数
		if (root == null) {
			return 0;
		}
		count2++;//在遍历时所有的结点都会访问到,每访问一个结点就将count2加一
		nodeCount2(root.left);
		nodeCount2(root.right);
		return count2;
	}
	
	// 求二叉树的结点数(方法三)
	public int nodeCount3(Node root) {
		int res = 0;// 记录结点的个数
		if (root == null) {// 空树直接返回0
			return 0;
		}
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node temp = stack.pop();
			res++;// 在遍历时所有的结点都会访问到,每访问一个结点就将res加一
			if (temp.left != null) {
				stack.push(temp.left);
			}
			if (temp.right != null) {
				stack.push(temp.right);
			}
		}
		return res;
	}

	//求第k层结点个数
	public int kLevelCount(Node root,int k) {
		if(root==null) {//空树直接返回0
			return 0;
		}
		if(k==1) {//k==1即求根节点的个数，直接返回1
			return 1;
		}
		return kLevelCount(root.left,k-1)+kLevelCount(root.right,k-1);//k层节点的个数=根节点左子树的k-1层节点个数+根节点右子树的k-1层节点个数
		
	}
	public static void main(String[] args) {
		BinaryTree binaryTree=new BinaryTree();
		Node root=binaryTree.BuildTree();
		System.out.println("二叉树的最大高度为(DFS):"+binaryTree.maxDepth1(root));//DFS求二叉树高度
		System.out.println("二叉树的最大高度为(BFS):"+binaryTree.maxDepth2(root));//BFS求二叉树高度
		System.out.println("二叉树结点的个数为(方法一)："+binaryTree.nodeCount1(root));
		System.out.println("二叉树结点的个数为(方法二)："+binaryTree.nodeCount2(root));
		System.out.println("二叉树结点的个数为(方法三)："+binaryTree.nodeCount3(root));
		System.out.println("二叉树叶子结点的个数为(方法一)："+binaryTree.leafCount1(root));
		System.out.println("二叉树叶子结点的个数为(方法二)："+binaryTree.leafCount2(root));
		System.out.println("二叉树叶子结点的个数为(方法三)："+binaryTree.leafCount3(root));
		System.out.printf("二叉树第%d层结点个数数为：%d",3,binaryTree.kLevelCount(root,3));
	}
}

class Node{
	char val;
	Node left;
	Node right;
	public Node(char val) {//Node的构造函数
		this.val=val;
	}
}
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

运行结果：

二叉树的最大高度为(DFS):4
二叉树的最大高度为(BFS):4
二叉树结点的个数为(方法一)：8
二叉树结点的个数为(方法二)：8
二叉树结点的个数为(方法三)：8
二叉树叶子结点的个数为(方法一)：4
二叉树叶子结点的个数为(方法二)：4
二叉树叶子结点的个数为(方法三)：4
二叉树第3层结点个数数为：4
1
2
3
4
5
6
7
8
9

该实例的二叉树图如下所示：