[数据结构与算法]【一起学数据结构与算法】全方面学习二叉树(下)

前言

此篇是对上篇二叉树的补充！

五、二叉树的基本操作

5.2 获取树中节点的个数(2种方法)

// 获取树中节点的个数 两种方法
    public static int nodeSize = 0;
    public int size(BTNode root) {
        if(root == null) {
            return 0;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
        return nodeSize;
    }

    public int size2(BTNode root) {
        if(root == null) {
            return 0;
        }
        int tmp = size2(root.left)+size2(root.right)+1;
        return tmp;
    }

5.3 获取叶子节点的个数(两种方法)

	int getLeafNodeCount(BTNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int tmp = getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
        return tmp;
    }

    public static int leafSize = 0;

    int getLeafNodeCount2(BTNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
        return leafSize;
    }

5.4 判断第K层节点的个数

	int getKLevelNodeCount(BTNode root,int k) {
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int tmp = getKLevelNodeCount(root.left, k - 1) +
                getKLevelNodeCount(root.right, k - 1);
        return tmp;
    }

5.5 获取二叉树的高度

	public int getHeight(BTNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

    public int getHeight2(BTNode root) {
        if (root == null) {
            return 0;
        }
        return getHeight2(root.left) > getHeight2(root.right)
                ? getHeight2(root.left) + 1 : getHeight2(root.right) + 1;
    }

5.6 检测值为val的元素是否存在

public BTNode find(BTNode root, char val) {
        if(root == null) {
            return null;
        }
        if(root.val == val) {
            return root;
        }
        BTNode ret1 = find(root.left,val);
        if(ret1 != null) {
            return ret1;
        }
        BTNode ret2 =  find(root.right,val);
        if(ret2 != null) {
            return ret2;
        }
        return null;
    }