二叉树高级应用：从基础到LeetCode实战

二叉树高级应用：从基础到LeetCode实战

引用

CSDN

1.

https://blog.csdn.net/2301_77954967/article/details/139360214

二叉树是数据结构中一种重要的树形结构，除了基本的遍历和搜索操作外，还有很多高级应用。本文将介绍二叉树的一些高级功能，包括查找第K层节点个数、判断是否为完全二叉树，以及两个LeetCode相关例题的解决方案。

查找第K层的节点个数

如上图所示，第一层有1个节点，第二层有2个节点，第三层有3个节点。实现这个功能相对简单，我们只需要在递归函数中传入一个表示当前层数的变量，然后递归左右子树。如果节点为空则返回0，如果当前节点位于第K层则返回1。

int TreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    
    // 子问题
    return TreeLevelKSize(root->left, k - 1)
        + TreeLevelKSize(root->right, k - 1);
}

判断是否为完全二叉树

首先需要区分满二叉树和完全二叉树的概念：

• 满二叉树：每一层的节点数都达到最大值，即如果深度为K，节点总数为2^k-1。
• 完全二叉树：对于深度为K的二叉树，其节点与深度为K的满二叉树中编号从1至n的节点一一对应。

两者的区别可以通过下图直观理解：

判断是否为完全二叉树可以使用层序遍历的方法：

1. 使用队列进行层序遍历，空节点也入队。
2. 遇到第一个空节点后，检查队列中是否还有非空节点。如果有，则不是完全二叉树。

下面是具体的代码实现：

bool TreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        // 遇到第一个空，就可以开始判断，如果队列中还有非空，就不是完全二叉树
        if (front == NULL)
        {
            break;
        }
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        // 如果有非空，就不是完全二叉树
        if (front)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

LeetCode 226：反转二叉树

这道题的思路相对简单，每个节点的左右子树交换即可完成反转。代码实现如下：

typedef struct TreeNode TreeNode;
struct TreeNode* invertTree(struct TreeNode* root) {
    if(root == NULL)
        return NULL;
    TreeNode* left = invertTree(root->left);
    TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

值得注意的是，即使先进行左右子树的交换再递归，也不会影响最终结果，因为二叉树本质上是一种链表结构。

LeetCode 110：平衡二叉树

平衡二叉树的定义是任意节点的左右子树高度差不超过1。可以通过递归计算每个节点的高度来判断是否平衡。

方法一：自顶向下递归

这种方法的时间复杂度较高，因为会重复计算节点的高度。

#define MAX(a,b) ((a)>(b)?(a):(b))
int height(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    return MAX(height(root->left),height(root->right))+1;
}
bool isBalanced(struct TreeNode* root) {
    if(root == NULL)
        return true;
    return (fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right));
}

方法二：自底向上递归

这种方法通过在计算高度的同时判断平衡性，避免了重复计算，时间复杂度更低。

#define MAX(a,b) ((a)>(b)?(a):(b))
int height(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if(leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1)
    {
        return -1;
    }
    else
    {
        return MAX(leftHeight, rightHeight) + 1;
    }
}
bool isBalanced(struct TreeNode* root) {
    return height(root) != -1;
}

通过以上分析和代码实现，我们可以更好地理解和掌握二叉树的高级应用及其相关算法。