二叉树（中）

目录

二叉树的基本操作

设置基本变量

 获取树中结点的个数

获取叶子结点个数

 获取第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. 遍历思路：把二叉树中的结点都遍历一遍
2. 子问题思路：根的左子树结点数 + 根的右子树结点数 + 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;}

关于这个子问题思路来得到二叉树结点个数的过程，我想来着重来说一下，因为实话说，我在这卡了一个下午，我会尽我最大努力把这点给讲明白。

 

1. 根据上面的代码，我们能看到root会经历 A -> B -> D 的过程。
2. 当root = D时，会进行先后进行 size2(root.left) 和 size2(root.right)。
3. 因为D的左右子树都是空，所以会先返回到D结点，然后返回size2(D.left) + size2(D.right) + 1/(0+0+1)，接着root = B，再进行对B的右子树结点的统计。
4. 其他结点的个数再依此类推，主要的思路是 把每个结点都当作一次 根结点，来进行返回。

这一点卡住我了一个下午，不过这也算是这一下午的收获，对吧。

下面的递归方式和这个有些类似，就不一一解释了，关键在于 把每个结点都当作一次 根结点。

获取叶子结点个数

叶子结点的特点是：它的左子树和右子树为空，所以可以通过判断这个条件来识别结点是否是叶子结点。

同样，这也可以分为遍历思路和子问题思路来实现

遍历思路

    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;
}