当前位置：首页 > article >正文

《二叉树》——4（Leetcode题目练习）

article 2024/9/19 9:19:54

前言：

题目一：《对称二叉树》

思路：

题目二：《单值二叉树》

思路：

题目三：《检查两颗树是否相同》

思路：

题目四：《前序遍历》

思路：

题目五：《另一颗子树》

思路：

题目六：《翻转二叉树》

思路：

题目七：《平衡二叉树》

思路：

前言：

本文将引出13道经典二叉树题目来帮助我们对于递归有更进一步学习。不仅能够锻炼我们对二叉树的理解，也能强化我们对递归算法的理解。一下是本文将涉及的题目：

《对称二叉树》《单值二叉树》《相同的树》《前序遍历》《另一颗子树》《翻转二叉树》《平衡二叉树》

题目一：《对称二叉树》

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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

bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2)
{
    if(root1 == NULL && root2 == NULL)
        return true;
    
    if(root1 == NULL || root2 == NULL)
        return false;
    
    if(root1->val != root2->val)
        return false;
    

    return (_isSymmetric(root1->left, root2->right)) && (_isSymmetric(root1->right, root2->left));

}

bool isSymmetric(struct TreeNode* root) {
    return _isSymmetric(root->left, root->right);   
}

思路：

首先我们需要知道这道题目的分治子问题，

1、根节点的左子树和右子树比较

2、分两次比较，左子树的右节点和右子树的左节点比较，左子树的左节点和右子树的右节点比较

题目二：《单值二叉树》

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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

    if(root->left)
    {
        if(root->val != root->left->val)
        {
            return false;
        }
    }
    if(root->right)
    {
        if(root->val != root->right->val)
        {
            return false;
        }
    }

    return isUnivalTree(root->left) && isUnivalTree(root->right);

}

思路：

同样是找分治子问题。

1、空节点不影响其它节点，所以当访问到空节点时直接return true即可

2、将左孩子的值与自己的值相比，再将右孩子的值与自己相比。

题目三：《检查两颗树是否相同》

力扣（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) || (q == NULL && p!= NULL))
    {
        return false;
    }

    if(p == NULL && q == NULL)
    {
        return true;
    }

    if(p->val == q->val)
    {
       return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }

    return false;

}

思路：

1、如果p为空且q不为空，或者，p不为空且q为空。return false;

2、如果两个节点都为空，则直接return true;

3、如果当前节点均不为空，则比较值如果相同那么，左子树和左子树比较，右子树和右子树比较

题目四：《前序遍历》

力扣（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 TreeSize(struct TreeNode* root)
{
    return (root == NULL)?0:TreeSize(root->left) + TreeSize(root->right) + 1;
}

void Preorder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
    {
        return;
    }

    a[(*pi)++] = root->val;
    Preorder(root->left, a, pi);
    Preorder(root->right, a, pi);
    

}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = TreeSize(root);
    int* a = (int*)malloc(sizeof(int)*n);
    *returnSize = n;
    int i = 0;
    Preorder(root, a, &i);
    return a;
    
}

思路：

本题目有几个点需要注意：

1、题目明确说明：“* Note: The returned array must be malloced, assume caller calls free().”

意思就是说作返回值的数组，必须要malloc开辟的

2、关于形参中的“int* returnSize”，并不是一个数组，它是统计数的节点个数，需要我们求出数的节点个数并改变returnSize。

我们都知道想要交换两个变量，利用函数应当传递地址而不是传递值，因为形参是实参的一份临时拷贝。

再说回思路。

首先，既然是返回数组，那么我们需要对树进行一次前序遍历，将每次经过的非空节点的val存放到我们开辟好的数组中，并且改变returnSize即可。

我们在之前讲解《链式二叉树》的blog中，有实现创建关于“统计节点数”的函数，在这里我就不过多赘述。

当我们开辟好数组后，同样通过我上面所讲解的，对于函数传递地址既可以真正改变变量的值。

所以我们设i为数组的下标那么我们在调用前序遍历void Preorder(struct TreeNode* root, int* a, int* pi)函数则需要利用指针来接受。

再通过前序遍历的基本思路即可完成本题目。

题目五：《另一颗子树》

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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


bool compare(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root == NULL && subRoot == NULL)
    {
        return true;
    }
    if(root == NULL || subRoot == NULL)
    {
        return false;
    }
    if(root->val != subRoot ->val)
    {
        return false;
    }
    return compare(root->left, subRoot->left) && compare(root->right, subRoot->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
    {
        return false;
    }

    return compare(root, subRoot) || isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);


}

思路：

1、比较两树根节点

2、若根节点相同则比较左子树再比较右子树

思路简单，但是在return 控制条件时较难理解。

题目六：《翻转二叉树》

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    if(root == NULL)
    {
        return NULL;
    }

    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

思路：

分别将左右子树各个节点的左右孩子进行交换，从下往上

题目七：《平衡二叉树》

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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

int TreeHeight(struct TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftheight = TreeHeight(root->left);
	int rightheight = TreeHeight(root->right);
	return (leftheight > rightheight) ? (leftheight + 1) : (rightheight + 1);
}

bool isBalanced(struct TreeNode* root) {
    if(root == NULL)
        return true;
    
    return fabs(TreeHeight(root->left) - TreeHeight(root->right))<=1 && isBalanced(root->left) && isBalanced(root->right);
}