数据结构二叉树应用实战：多场景练习题强化巩固

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root)
 {
    if(root==NULL)
    {
        return true;
    }
    if(root->left!=NULL&&root->left->val!=root->val)
    return false;
    if(root->right!=NULL&&root->right->val!=root->val)
    return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p == NULL && q == NULL)
    {
        return true;
    }
    if(p == NULL || q == NULL)
    {
        return false;
    }
    if(p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 bool isSameTree(struct TreeNode* a,struct TreeNode* b)
 {
    if(a==NULL&&b==NULL)
    {
        return true;
    }
    if(a==NULL||b==NULL)
    {
        return false;
    }
    if(a->val!=b->val)
    {
        return false;
    }
    return isSameTree(a->left,b->right)&&isSameTree(a->right,b->left);
 }
bool isSymmetric(struct TreeNode* root)
 {
    return isSameTree(root->left,root->right);
}

作者：星轨初途
链接：https://leetcode.cn/problems/symmetric-tree/solutions/3837280/jian-dan-dui-cheng-er-cha-shu-by-flamboy-e5ei/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

// 作用：统计二叉树的节点总个数
 int BinarTreeSize(struct TreeNode* a)
 {
    if(a==NULL)
    {
        return 0;
    }
    return BinarTreeSize(a->left)+BinarTreeSize(a->right)+1;
 }

// 作用：递归实现二叉树的前序遍历，并将节点值存入数组中
 void preOrder(struct TreeNode* root,int *arr,int *i)
 {
    if(root==NULL)
    {
        return ;
    }
    arr[(*i)++]=root->val;
    preOrder(root->left,arr,i);
    preOrder(root->right,arr,i);
 }

// 作用：主函数，完成二叉树前序遍历结果的数组封装（分配内存+执行遍历）
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    *returnSize = BinarTreeSize(root);
    int* arr = (int*)malloc(sizeof(int)*(*returnSize));
    //前序遍历
    int i = 0;
    preOrder(root,arr,&i);
    return arr;
}
  

作者：星轨初途
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/3837311/er-cha-shu-de-qian-xu-bian-li-ti-jie-by-k9mzh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 判断两棵树是否完全相同（节点值和结构都一致）
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p == NULL && q == NULL)
    {
        return true; // 两棵树都为空，视为相同
    }
    if(p == NULL || q == NULL)
    {
        return false; // 一棵空一棵非空，视为不同
    }
    if(p->val != q->val)
    {
        return false; // 节点值不同，视为不同
    }
    // 递归判断左右子树是否都相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}


bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root == NULL)
    {
        return false; // 主树为空时，无法包含任何子树（除非subRoot也为空，本题默认subRoot为有效子树）
    }
    if(isSameTree(root,subRoot))
    {
        return true; // 当前主树节点与子树完全相同，直接返回true
    }
    // 递归判断子树是否是左子树的子树，或是否是右子树的子树（只要其一满足即可）
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

作者：星轨初途
链接：https://leetcode.cn/problems/subtree-of-another-tree/solutions/3837255/ling-yi-ke-shu-de-zi-shu-ti-jie-by-flamb-onx7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。