二叉树（中）
目录
二叉树的基本操作
设置基本变量
获取树中结点的个数
获取叶子结点个数
获取第K层结点的个数
获取二叉树高度
检测值为value的元素是否存在
二叉树的基本操作
如果需要了解树和二叉树的基本内容，可以转至：二叉树（上）-CSDN博客
二叉树的基本操作包括但不限于：
- 获取树中结点的个数
- 获取叶子结点的个数
- 获取第K层结点的个数
- 获取二叉树的高度
- 检测值为value的元素是否存在
本文所用到的二叉树为简单创建的二叉树，为减少相对的学习成本。
设置基本变量
这里和上一篇文章：二叉树（上）-CSDN博客 中设置的基本变量一致，所以直接给出代码。
下图是简单实现的二叉树图
public class BinaryTree {
static class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
public TreeNode createTree(){
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
E.right = H;
C.left = F;
C.right = G;
return A;
}获取树中结点的个数
获取树中结点个数有两种思路：
- 遍历思路：把二叉树中的结点都遍历一遍
- 子问题思路：根的左子树结点数 + 根的右子树结点数 + 1
我们可以先把这两个思路都走一遍，不过后面部分方法会用子问题思路来实现。
之前实现二叉树前序、中序和后序遍历的时候，用到了递归，这里的方法也要用到递归，说到底就是根结点的改变，来一步步进行的。
遍历思路
// 获取树中节点的个数
// 遍历思路
public static int nodeSize = 0;
public int size(TreeNode root){
if(root == null){
return -1;
}
nodeSize++;
size(root.left);
size(root.right);
return nodeSize;
}子问题思路
public int size2(TreeNode root){
if(root == null){
return 0;
}
return size2(root.left) + size2(root.right) + 1;
}关于这个子问题思路来得到二叉树结点个数的过程，我想来着重来说一下，因为实话说，我在这卡了一个下午，我会尽我最大努力把这点给讲明白。
- 根据上面的代码，我们能看到root会经历 A -> B -> D 的过程。
- 当root = D时，会进行先后进行 size2(root.left) 和 size2(root.right)。
- 因为D的左右子树都是空，所以会先返回到D结点，然后返回size2(D.left) + size2(D.right) + 1/(0+0+1)，接着root = B，再进行对B的右子树结点的统计。
- 其他结点的个数再依此类推，主要的思路是 把每个结点都当作一次 根结点，来进行返回。
这一点卡住我了一个下午，不过这也算是这一下午的收获，对吧。
下面的递归方式和这个有些类似，就不一一解释了，关键在于 把每个结点都当作一次 根结点。
获取叶子结点个数
叶子结点的特点是：它的左子树和右子树为空，所以可以通过判断这个条件来识别结点是否是叶子结点。
同样，这也可以分为遍历思路和子问题思路来实现
遍历思路
public static int leafSize = 0;
public int getLeafNodeCount2(TreeNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
leafSize++;
}
getLeafNodeCount2(root.left);
getLeafNodeCount2(root.right);
return leafSize;
}子问题思路
// 获取叶子节点的个数
public int getLeafNodeCount(TreeNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}获取第K层结点的个数
这里采用子问题的思路来进行，并且从根结点（也就是第二层开始进行）
第k层结点的个数 = 根的左子树第k-1层结点数 + 根的右子树第k-1层节点数。
// 获取第K层节点的个数
public 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);
}
获取二叉树高度
要获取二叉树的高度，用子问题的思路来看，便是 根的左子树 和 根的右子树高度的最大值 + 1.
// 获取二叉树的高度
public int getHeight(TreeNode root){
if(root == null){
return 0;
}
int leafHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.max(leafHeight, rightHeight) + 1;
}
检测值为value的元素是否存在
子问题思路，通过对根的左右子树进行遍历，然后判断对应值是否是和value值相等。
//时间复杂度：O(N)
public TreeNode findVal(TreeNode root, char val){
if(root == null){
return root;
}
if(root.val == val){
return root;
}
TreeNode leftT = findVal(root.left, val);
if(leftT != null){
return leftT;
}
TreeNode rightT = findVal(root.right, val);
if (rightT != null) {
return rightT;
}
return null;
}