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