java数据结构_二叉树_5.5
2.7 二叉树的相关操作
1. size方法 获取二叉树元素个数
思路：遍历思路，在前面文章中，前序 中序 后序遍历的时候，会把树中的所有结点遍历一次。可以添加一个计数器，遍历一个结点就加一次。
于是有如下代码：
public int size = 0; //定义一个成员变量size
public int nodeSize(TreeNode root) {if(root == null) return 0;size++;nodeSize(root.left);nodeSize(root.right);return size;
}在IDEA中测试符合预期，但还是思考，上面的方法，也没有利用到这个方法的返回值。
换个角度，以子问题的思路来思考：要算当前root总共有多少个结点，其实就等于：当前root结点的左子树的结点个数 + 当前root结点的右子树的结点个数 + 1。
于是有如下代码：
public int nodeSize(TreeNode root) {int size = 0;if(root == null) return size;int leftSize = nodeSize(root.left);int rightSize = nodeSize(root.right);return leftSize + rightSize + 1;
}该代码仍是化大树为小树，逐个解决子问题过程。
下图为部分递归过程，注意先递出去，再归回来
2. getLeafSize方法 得到二叉树叶子结点个数
先回忆概念，叶子结点也就是度为0的结点，也就是左右子树均为null的结点
于是有如下代码：
public int leaveSize = 0;public int getLeaveSize(TreeNode root) {if(root == null) return leaveSize;if(root.left == null && root.right == null) {leaveSize++;}getLeaveSize(root.left);getLeaveSize(root.right);return leaveSize;
}同样的，也可以换一种子问题思路来考虑，要求当前root有多少个叶子结点，其实就是相当于求root左树的叶子结点的个数 + root右树的叶子结点的个数
于是有如下代码：
public int getLeaveSize(TreeNode root) {if(root == null) return 0;if(root.left == null && root.right == null) {return 1;}int leftLeaveSize = getLeaveSize(root.left);int rightLeaveSize = getLeaveSize(root.right);return leftLeaveSize + rightLeaveSize;
}下图为部分递归过程，注意先递出去，再归回来
3. getKLevelNodeCount方法 获得第K层的结点的个数
root这棵树的第K层的结点的个数 = root.left第K - 1层的结点的个数 + root.right第K - 1层的结点的个数
如上图，若像求第3层的结点的个数，就等于求root(A).left(B)的第二层 + root(A).right(C)的第二层
于是有代码如下：
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);
}遍历模拟图为：
4. getHeight方法 获得二叉树高度
分析：整棵树的高度 = root左树的高度 + root右树的高度 + 1
于是有如下代码：
public int getTreeHeight(TreeNode root) {if(root == null) return 0;int leftTreeHeight = getTreeHeight(root.left);int rightTreeHeight = getTreeHeight(root.right);return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1;
}如下图为递归的部分过程
5. find方法 检查二叉树是否存在值为val的元素
find方法，对比之前的数据结构查找，也是在整个数据结构中遍历一次，定义一个标识，如果有，就标识为ture，否则为false。
于是有如下代码：补充：下面代码是使用先序遍历来进行的查找
public boolean find(TreeNode root, char value) {if(root == null) return false;if(root.val == value) {return true;}boolean leftFlg = find(root.left, value);if(leftFlg == true) {return true;}boolean rightFlg = find(root.right, value) {return true;} return false;
}