leetcode刷题第十三天——二叉树Ⅲ

news/2025/2/22 6:24:30

本次刷题顺序是按照卡尔的代码随想录中给出的顺序

翻转二叉树

226. 翻转二叉树

/**
 * 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* tmp;
    //交换左右子树
    tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    //在对左右子树分别进行翻转
    root->left = invertTree(root->left);
    root->right = invertTree(root->right);
    return root;
}

对称二叉树

d101. 对称二叉树

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

/*总体思路，对于当前结点而言，其左孩子与右孩子的结点值相同
 *左孩子的(左、右)孩子的结点值与右孩子的(右、左)孩子的结点值相同*/

bool isSymmetree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL) return true;
    else if(p != NULL && q != NULL) {
        return (p->val == q->val && isSymmetree(p->left, q->right) \
        && isSymmetree(p->right, q->left));
    }else {
        return false;
    }
}

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

相同的树

100. 相同的树

/**
 * 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;
    else if(p != NULL && q != NULL) {
        return (p->val == q->val && isSameTree(p->right, q->right) \
        && isSameTree(p->left, q->left));
    }else {
        return false;
    }
}

另一颗树的子树

572. 另一棵树的子树

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

/*建立在“判断两棵树是相同的树”的基础之上，
 *总体思路：如果以当前结点为根的树与指定树subRoot相同，则直接返回true
 *否则，分别查看以当前结点的左、右孩子结点为根的树与subRoot是否相同，有则返回true
 *否则，返回false*/

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL) return true;
    else if(p != NULL && q != NULL) {
        return (p->val == q->val && isSameTree(p->left, q->left) && \
        isSameTree(p->right, q->right));
    }else return false;
}

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

二叉树的最大深度

104. 二叉树的最大深度

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

/*利用层序遍历的框架，即可统计最大深度，因为内层循环就是遍历一层的结点，外层循环就是遍历所有层，
 *故而，每进行依次外层循环，层数加1，跳出外层循环后，返回层数即为最大深度*/

int maxDepth(struct TreeNode* root) {
    if(root == NULL) return 0;
	struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 10001);
    struct TreeNode* tmp;
    int rear = -1, mid_rear, front = -1, sum = 0;
    st[++rear] = root;
    mid_rear = rear;
    while(rear != front) {
        while(mid_rear != front) {
            tmp = st[++front];
            //判断子树是否需要入队列
            if(tmp->left) st[++rear] = tmp->left;
            if(tmp->right) st[++rear] = tmp->right;
        }
        sum++;
        mid_rear = rear;
    }
    return sum;
}

二叉树的最小深度

111. 二叉树的最小深度

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

/*也是建立在层次遍历的基础之上，如果内层循环在遍历当前层结点时，
 *出现某个结点左、右子树均为NULL，则直接返回当前层的深度*/

int minDepth(struct TreeNode* root) {
    if(root == NULL) return 0;
	struct TreeNode** st = malloc(sizeof(struct TreeNode*) * 100001);
    struct TreeNode* tmp;
    int rear = -1, mid_rear, front = -1, sum = 0;
    st[++rear] = root;
    mid_rear = rear;
    while(rear != front) {
        sum++;
        while(mid_rear != front) {
            tmp = st[++front];
            //判断子树是否需要入队列
            if(tmp->left) st[++rear] = tmp->left;
            if(tmp->right) st[++rear] = tmp->right;
            if(!tmp->left && !tmp->right) return sum;
        }
        mid_rear = rear;
    }
    return sum;
}

完全二叉树的结点个数

222. 完全二叉树的节点个数

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

/*利用满二叉树的性质进行求解
 *当前结点，如果左、右深度一致，说明是满二叉树，直接由公式得到节点数
 *如果左、右深度不一致，则返回左子树结点数+右子树结点数+1
 *
 *为什么可以这么做？因为，完全二叉树除了最后一层未满，其它层均是满的*/

int countNodes(struct TreeNode* root) {
    if(root == NULL) return 0;
    struct TreeNode* l_child = root->left, * r_child = root->right;
    int l_cnt = 0, r_cnt = 0;
    while(l_child != NULL) {
        l_cnt++;
        l_child = l_child->left;
    }
    while(r_child != NULL) {
        r_cnt++;
        r_child = r_child->right;
    }
    //若向左和向右遍历深度一致，说明是满二叉树，可以直接求解结点个数
    if(l_cnt == r_cnt) return (2  <<  l_cnt) - 1;
    else return (countNodes(root->left) + countNodes(root->right) + 1);
}

平衡二叉树

110. 平衡二叉树

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

/*对于每个结点，求其左右子树的高度
 *所有结点，左右子树高度差不应超过1*/

//求得树的高度
int treeDeepth(struct TreeNode* p) {
    if(p == NULL) return 0;
    else return fmax(treeDeepth(p->left), treeDeepth(p->right)) + 1;
}

bool isBalanced(struct TreeNode* root) {
    if(root == NULL) return true;
    //对于当前结点，两棵子树的高度差小于等于1，则判断结点的左右子树是否为平衡二叉树
    if(fabs(treeDeepth(root->left) - treeDeepth(root->right)) <= 1) {
        return isBalanced(root->left) && isBalanced(root->right);
    }else return false;//对于当前结点，两棵子树的高度差大于1，则直接返回错误
}

左叶子之和

404. 左叶子之和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int sumOfLeftLeaves(struct TreeNode* root) {
    //如果为空，则必定返回0
    if(root == NULL) return 0;
    //如果当前结点的左孩子左右子树均为空，则当前结点的左孩子是左叶子
    if(root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
        return root->left->val + sumOfLeftLeaves(root->right);
    }else {//如果当前结点左孩子为空，或者其左孩子左右子树不为空
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
}

找树左下角的值

513. 找树左下角的值

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

/*找最左下结点的值，依照层次遍历的框架，最后一层的第一个结点就是最左下的结点*/

int findBottomLeftValue(struct TreeNode* root) {
    struct TreeNode** qu = malloc(sizeof(struct TreeNode*) * 10000);
    struct TreeNode* tmp;
    int rear = -1, mid_rear, front = -1, res;
    qu[++rear] = root;
    do {
        mid_rear = rear;
        res = qu[front + 1]->val;
        while(front != mid_rear) {
            tmp = qu[++front];
            if(tmp->left) qu[++rear] = tmp->left;
            if(tmp->right) qu[++rear] = tmp->right;
        }
    }while(rear != front);
    return res;
}

最大二叉树

654. 最大二叉树

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

/*按照先序遍历的思想，先构造根节点，再构造左子树，最后构造右子树
 *需要配合查找数组最大值下标的程序进行构造*/

int FindMaxIdx(int* nums, int start, int end) {
    int idx = start, max = INT_MIN, max_idx;
    while(idx <= end) {
        if(nums[idx] > max) {
            max = nums[idx];
            max_idx = idx;
        }
        idx++;
    }
    return max_idx;
}

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    if(numsSize == 0) return NULL;
    int max_idx = FindMaxIdx(nums, 0, numsSize - 1);
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = nums[max_idx];
    root->left = constructMaximumBinaryTree(nums, max_idx);
    root->right = constructMaximumBinaryTree(nums + max_idx + 1, numsSize - max_idx - 1);
    return root;
}

合并二叉树

617. 合并二叉树

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

/*在遍历过程中，两个结点均存在，则返回结点值为两者之和，
 *只有一者存在，直接返回该结点，
 *两者均不存在，则直接返回NULL*/

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    if(root1 == NULL && root2 == NULL) return NULL;
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    if(root1 != NULL && root2 != NULL) {
        root->val = root1->val + root2->val;
        root->left = mergeTrees(root1->left, root2->left);
        root->right = mergeTrees(root1->right, root2->right);
    }else {
        if(root1 != NULL) {
            root = root1;
        }else root = root2;
    }
    return root;
}

递归用得挺多的，后面可以尝试迭代算法的实现。

递归需要考虑，递归的终止条件是什么？递归程序的单层逻辑是什么？

需要熟练掌握二叉树的四种遍历方式的框架，一般都是以此为突破口进行编程


http://www.niftyadmin.cn/n/5861783.html

相关文章

如何利用 Vue 的生命周期钩子进行初始化和清理操作？

如何利用 Vue 的生命周期钩子进行初始化和清理操作？

一、初始化操作的核心钩子 1. created&#xff08;选项式API&#xff09; export default {data() {return { user: null };},created() {// 适合初始化数据、发起非DOM操作请求this.fetchUser();},methods: {async fetchUser() {const response await fetch(/api/user);thi…
阅读更多...
什么容错性以及Spark Streaming如何保证容错性

什么容错性以及Spark Streaming如何保证容错性

一、容错性的定义 容错性是指一个系统在发生故障或崩溃时&#xff0c;能够继续运行并提供一定服务的能力。在网络或系统中&#xff0c;这通常涉及到物理组件损坏或软件失败时系统的持续运行能力。容错系统的关键特性包括负载平衡、集群、冗余、复制和故障转移等。 二、Spark …
阅读更多...
win10把c盘docker虚拟硬盘映射迁移到别的磁盘

win10把c盘docker虚拟硬盘映射迁移到别的磁盘

c盘空间本身就比较小、如果安装了docker服务后&#xff0c;安装的时候没选择其他硬盘&#xff0c;虚拟磁盘也在c盘会占用很大的空间&#xff0c;像我的就三十多个G&#xff0c;把它迁移到其他磁盘一下子节约几十G 1、先输入下面命令查看 docker 状态 wsl -l -v 2、如果没有停止…
阅读更多...
oracle怎么创建定时任务

oracle怎么创建定时任务

在Oracle中创建定时任务&#xff0c;可以使用DBMS_SCHEDULER包&#xff0c;以下是创建定时任务的详细步骤&#xff1a; 1. 创建作业 需要创建一个作业&#xff0c;用于执行定时任务&#xff0c;作业是一组SQL语句或PL/SQL代码&#xff0c;可以定期执行。 BEGINDBMS_SCHEDULE…
阅读更多...
从DeepSeek大爆发看AI革命困局：大模型如何突破算力囚笼与信任危机？

从DeepSeek大爆发看AI革命困局：大模型如何突破算力囚笼与信任危机？

目录 从DeepSeek大爆发看AI革命困局&#xff1a;大模型如何突破算力囚笼与信任危机&#xff1f; 小瓜有话说——为什么想写这篇博文 一、算力军备竞赛下的临时繁荣 1、技术奇点的陷阱 2、行业困境 二、三类企业的生存实验 1. 守旧派的黄昏&#xff1a;参数崇拜者的绝击 …
阅读更多...
pycharm将当前项目上传到github

pycharm将当前项目上传到github

要将当前项目从 PyCharm 上传到 GitHub&#xff0c;你可以按照以下步骤操作&#xff1a; 1. 创建一个 GitHub 仓库 登录到 GitHub。点击右上角的 按钮&#xff0c;然后选择 New repository。填写仓库名称、描述等信息&#xff0c;点击 Create repository。 2. 在 PyCharm 中…
阅读更多...
C++ 设计模式-备忘录模式

C++ 设计模式-备忘录模式

游戏存档实现&#xff0c;包括撤销/重做、持久化存储、版本控制和内存管理 #include <iostream> #include <memory> #include <deque> #include <stack> #include <chrono> #include <fstream> #include <sstream> #include <ct…
阅读更多...
WPF 中显示图形的方式深度解析

WPF 中显示图形的方式深度解析

一、引言 Windows Presentation Foundation（WPF）凭借其强大的图形渲染能力，为开发者打造美观、交互性强的桌面应用程序提供了有力支持。在 WPF 里，有多种显示图形的方式，每种方式都有独特的用途和特点。本文将详细介绍 DrawingImage、Shape、Image、GeometryDrawing、Dra…
阅读更多...
最新文章

Copyright @ 2022~2023