【初阶数据结构篇】二叉树算法题

2024-10-09 18:56:48 浏览数 (1)

二叉树算法题

前言

  • 本篇的算法题涉及到链式结构二叉树的实现方法
  • 可参考：
  • 二叉链实现方法上篇
  • 二叉链实现方法下篇

单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时，才返回 true；否则返回 false。

  • 拿到根节点，和左右孩子比较
    • 左孩子不为空就判断是否相等，右孩子同理
  • 以相同方式递归左右子树
  • 结束条件
    • root为空，不影响，返回true
    • 若不相等直接返回false
代码语言：javascript复制
/**
 * 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 && root->val != root->left->val)
        return false;
    if (root->right && root->val != root->right->val)
        return false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

  • 如果两个二叉树都为空，则两个二叉树相同。
  • 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
  • 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程。
代码语言：javascript复制
/**
 * 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);
}

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。（root不为空）

  • 二叉树是否对称，即左右子树是否对称
  • 把左右子树当做单独的两棵树来比较
  • 在上面一道相同的树中，我们是通过同时递归两棵树的左子树判断是否相等，对右子树同理
  • 而本题则是对称，即判断一棵树的左子树和右子树（以及右子树和左子树）是否相等
  • 所以我们同时递归一棵树的左子树和另一棵树的右子树（以及前者的右子树和后者左子树）即可
  • 将上面代码略微修改即可
代码语言：javascript复制
/**
 * 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->right) && isSameTree(p->right, q->left);
}

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

另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树

  • 思路很简单，依次递推，到每个结点时判断即可
    • 在左子树或者右子树找到了直接返回就行，注意是||不是&&
  • 对于每个结点都当作根节点，来判断以这个结点为根节点的树和subRoot是否相等
  • 判断相等还是使用上面的isSameTree方法
代码语言：javascript复制
/**
 * 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;
    if (isSameTree(root, subRoot))
        return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

  • 本题的特殊之处在于它的返回值是一个数组，所以我们需要先为数组动态开辟一块空间
  • 第一步：计算二叉树结点个数
  • 第二步：前序遍历并依次插入
    • 自己写一个前序遍历函数
    • 在插入时，使用传址调用的方式。不能创建全局变量，否则只能调用一次这个函数
代码语言：javascript复制
/**
 * 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().
 */
 typedef struct TreeNode TreeNode;
 int TreeSize(TreeNode* root)
 {
    if(root==NULL)
    return 0;
    return 1 TreeSize(root->left) TreeSize(root->right);
 }

 void Preorder(TreeNode* root,int* arr,int* pi)
 {
    if(root==NULL)
    return;
    arr[(*pi)  ]=root->val;
    Preorder(root->left,arr,pi);
    Preorder(root->right,arr,pi);
 }
 
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize=TreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    Preorder(root,arr,&i);
    return arr;
}

本题如换做中序和后序遍历，直接调换插入数据顺序即可，其它思路都一样 中序遍历题目 后序遍历题目

以上就是二叉树算法题的内容啦，各位大佬有什么问题欢迎在评论区指正，您的支持是我创作的最大动力！❤️

二叉树 数据结构 root 遍历 算法

0 人点赞