二叉树结点、叶子结点个数，高度，第K层几个结点-蒲公英云

二叉树结点、叶子结点个数，高度，第K层几个结点

文章目录

- - 结点个数
  - 叶子结点个数
  - 二叉树高度
  - 第K层几个结点

二叉树的结点个数
二叉树叶子结点个数
二叉树第K层结点个数
二叉树的高度

在二叉树中，我们经常用到递归，再用递归的时候，经常会用到：递推公式，终止条件
递推公式：如果左子树和右子树的结果都有了，按照这个二叉树有三个结点往下操作
终止条件：递归一般都必须有终止条件，按照二叉树的五种基本形态考虑终止条件会比较简单一点
最后就是要考虑递归函数中的参数会不会发生改变

结点个数

递推公式：左子树结点个数 + 右子树结点个数 + 1
终止条件：空树返回0

int GetTreeSize(BNode *root)
    { 
        if (root == NULL)
        { 
            return 0;
        }
        return GetTreeSize(root->left) + GetTreeSize(root->right) + 1;
    }

叶子结点个数

递推公式：左子树叶子结点 + 右子树叶子结点
终止条件：空树返回0
如果一个结点左右孩子都为NULL，返回1

int GetLeafSize(BNode *root)
    { 
        if (root == NULL)
        { 
            return 0;
        }
        if (root->left == NULL && root->right == NULL)
        { 
            return 1;
        }
        return GetLeafSize(root->left) + GetLeafSize(root->right);
    }

二叉树高度

递推公式：MAX(左子树高度，右子树高度) + 1，就是较大值 + 1
终止条件：空树，返回0

#define MAX(a, b) (a) > (b) ? (a) : (b)
    int GetTreeHeight(BNode *root)
    { 
        if (root == NULL)
        { 
            return 0;
        }
        int height1 = GetTreeHeight(root->left);
        int height2 = GetTreeHeight(root->right);
        return MAX(height1, height2) + 1;
    }

第K层几个结点

递推公式：左子树K层结点个数 + 右子树K层结点个数
终止条件：空树，返回0
K== 1，返回1，表示只有一个结点，高度为1

int GetTreeKSize(BNode *root, int k)
    { 
        assert(k > 0);
        if (root == NULL)
        { 
            return 0;
        }
        if (k == 1)
        { 
            return 1;
        }
        return GetTreeKSize(root->left, k--) + GetTreeKSize(root->right, k--);
    }