LeetCode-二叉树OJ题

用户10923087

发布于 2024-01-23 14:31:58

1150

发布于 2024-01-23 14:31:58

文章被收录于专栏：我的计算机成长

1.单值二叉树

965. 单值二叉树

先判断这棵树是否为空，如果是空树则是true。再判断左子树是否为空，并且左子树的值val和当前节点的val不相同，如果这左子树不为空且val不等于root的val则返回false，再使用相同方式判断右子树。最后递归一下左右子树即可，只有左右子树有一个返回false，则整体返回false。

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

}

2.求二叉树的最大深度

104. 二叉树的最大深度

首先先进行判空，返回0。然后声明两个变量m和n分别代表树的左右深度，并在这里使用递归，分别赋值他们的左右子树，这里能起到遍历作用（搜索）。我们再用三目判断来给它赋值，取高的那一个，因为树的最大深度就是根的高度，所以这里我们还要在后面加上一，即补充从根子树到根的高度.

int maxDepth(struct TreeNode* root) 
{
    int m=0;
    int n=0;
    if(root==NULL)
    {
        return 0;
    }
    else
    {
        m=maxDepth(root->left);
        n=maxDepth(root->right);
    }
    return m>n?m+1:n+1;
    
}

3.翻转二叉树

226. 翻转二叉树

翻转一颗二叉树首先保存住当前节点的左右子树，然后将保存的左子树left放在right的位置，再递归左右子树即可。

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

4.镜像二叉树

101. 对称二叉树

这一题其实和相同二叉树这个题是很相似的，我们可以直接把那个代码拷贝过来使用，这一题的讲解在http://t.csdnimg.cn/ArwMx

差别在于最后的递归，相同的树是左子树和右子树进行比较，那么镜像二叉树就是左子树和右子树进行比较。

bool isSymmetricTree(struct TreeNode* p,struct TreeNode* q)
{
    //都为空
    if(q==NULL&&p==NULL)
        return true;
    //一个为空
    if(q==NULL||p==NULL)
        return false;
    if(q->val!=p->val)
        return false;
    return isSymmetricTree(p->left,q->right)&&isSymmetricTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) 
{
    return isSymmetricTree(root->left,root->right);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

镜像