二叉树经典14题——初学二叉树必会的简单题

2023-04-18 83

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二叉树经典14题——初学二叉树必会的简单题

此篇皆为leetcode、牛客中的简单题型和二叉树基础操作，无需做过多讲解，仅付最优解。有需要的小伙伴直接私信我~

正文

1.二叉树的节点个数

int BinaryTreeSize(BTNode* root)
{
  return root == NULL ? 0 : 
           BinaryTreeSize(root->left) + 
           BinaryTreeSize(root->right) + 1;
}

2.二叉树叶子节点个数

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

3.二叉树第K层节点个数

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

4.查找值为X的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType data)
{
  if (root == NULL)
    return NULL;
  if (root->data == data)
    return root;
  BTNode* ret1 = BinaryTreeFind(root->left, data);
  if (ret1)
    return ret1;
  BTNode* ret2 = BinaryTreeFind(root->right, data);
  if (ret2)
    return ret2;
  return NULL;
}

5.leetcode——二叉树的最大深度

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

6.leetcode——单值二叉树

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

7.leetcode——相同的树

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);
}

8.二叉树的前序遍历

void PrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", root->data);//前序在前
  PrevOrder(root->left);
  PrevOrder(root->right);
}

9.二叉树的中序遍历

void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->data);//中序在中
  InOrder(root->right);
}

10.二叉树的后序遍历

void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);//后序在后
}

11.二叉树的层序遍历

//需自己实现队列的数据结构
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
  else
    return;
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    printf("%d ", front->data);
    QueuePop(&q);
    if(front->left)
      QueuePush(&q, front->left);
    if(front->right)
      QueuePush(&q, front->right);
  }
  printf("\n");
  QueueDestroy(&q);
}

12.leetcode——另一棵树的子树

//判断两树是否相同（复用“相同的树”解题代码）
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;
    if(isSametree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

13.二叉树的构建及遍历

#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
    int val;
     struct TreeNode *left;
     struct TreeNode *right;
 };
struct TreeNode* rebuildTree(char* str,int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = str[(*pi)++];
    root->left = rebuildTree(str,pi);
    root->right = rebuildTree(str,pi);
    return root;
}
void TreeDestory(struct TreeNode* root)
{
    if(root==NULL)
        return;
    TreeDestory(root->left);
    TreeDestory(root->right);
    free(root);
}
void InOrder(struct TreeNode* root)
{
  if (root == NULL)
  {
    return;
  }
  InOrder(root->left);
  printf("%c ", root->val);
  InOrder(root->right);
}
int main() {
    char str[100];
    scanf("%s",str);
    int i=0;
    struct TreeNode* root = rebuildTree(str,&i);
    InOrder(root);
    TreeDestory(root);
    return 0;
}

14.leetcode——对称二叉树

bool _isSymmetric(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 _isSymmetric(p->left, q->right) &&
    _isSymmetric(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {
  return root == NULL ? 0 : _isSymmetric(root->left, root->right);
}