文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共13篇）

题解 | #序列化二叉树#

这道题本身挺简单的，但是坑是真的多，给我整破防了。先说一下大概的思路，直接用层序遍历来序列化。序列化的时候使用一个队列来辅助将结点值拼接到字符串上，节点为空则拼接#。反序列化时同理，使用队列来辅助反序列化，创建好的节点先入队，并且查看队头结点的情况，若其左结点为空，则将该结点设为队头结点的左结点，...

C++ 字符串二叉树队列

2021-10-11

0 431

题解 | #把二叉树打印成多行#

之前做过一道一模一样但是名字不同的题。这次就当是复习了。思路就不再写了，可以点这里看。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int ...

C++ 二叉树广度优先搜索

2021-10-11

0 349

题解 | #对称的二叉树#

最开始尝试直接递归原树进行比较，但是思路有问题。退而求其次，直接深拷贝原树，再比较两树。在写比较函数的过程中，我发现之所以最开始原树比较不行，应该是递归函数的比较逻辑出问题了，所以在写完这种方法后继续回头研究原树比较的方法。 /* struct TreeNode { int val; ...

C++ 二叉树

2021-10-11

0 427

题解 | #二叉树的下一个结点#

根据中序遍历的规则，可以知道，当该结点有右子树时，返回其右子树最左边的结点。当该结点没有右子树时，则需要向上寻找第一个其左子树中包含该结点的结点。根据这两种需求，分别写两个函数，一个通过递归找最左边的子结点，一个通过递归找向上第一个在左子树中包含该结点的点。根结点由于其next域为空所以需要做特殊处...

C++ 二叉树递归

2021-10-09

0 372

题解 | #平衡二叉树#

核心思想是递归。首先写一个递归函数来返回树的高度，然后主函数中递归调用该函数比较左右子树的高度。没有什么特别需要注意的点，就是时间复杂度和空间复杂度有点高。但是也没有想象的那么高。 class Solution { public: bool IsBalanced_Solution(Tree...

C++ 二叉树

2021-10-09

0 385

题解 | #二叉树中和为某一值的路径#

深度优先遍历题目的变种。只需要在遍历时多传两个参数，一个用于记录路径和，一个用于记录遍历过的结点即可。这里有个小坑需要注意，最开始在递归传参时使用了引用传参，导致递归返回后参数不回还原，需要改为值传参。果然引用传参还是存在危险的，需要稍用。 /* struct TreeNode { int va...

C++ 深度优先搜索二叉树

2021-10-09

0 366

题解 | #从上往下打印二叉树#

二叉树的层序遍历，较为基础。首先用一个二维数组将不同层的结点分开保存，然后将该二维数组的数依次输入到结果数组中即可。遍历过程中使用一个level变量来传递层数信息。 /* struct TreeNode { int val; struct TreeNode *left; struct Tree...

C++ 二叉树广度优先搜索

2021-10-08

0 410

题解 | #二叉树的镜像#

开始看到题目中说有原地算法，想挑战一下的，但是想了一会没什么思路，还是用常规的遍历解法来做了。逻辑十分简单，遍历头结点，交换左右子树，再依次遍历左右子树，直到遍历所有结点。使用递归进行遍历，时间复杂度为O(n)，同时需要维护一个递归栈，空间复杂度为O(n),满足题目要求。 /** * stru...

C++ 二叉树

2021-10-08

0 398

题解 | #树的子结构#

这题的基本思路很简单，难在对于情况的判断。上来看题首先确定题目中要遍历二叉树，并且还需要一个方法来判断是否有相同的结构。注意，这里判断的逻辑与判断两树是否相同基本类似。处理起来就是通过遍历原始树的结点，对每一个结点都调用判断结构的方法，若找到一个结点返回true，则直接返回true。这里说一下判断两...

C++ 二叉树分治链表

2021-10-08

0 378

题解 | #重建二叉树#

看题目首先确定采用分治的思想，通过题目给出的先序遍历与中序遍历确定头结点，然后通过该头结点得到两个子树的先序遍历与中序遍历，重复该过程，最后就可以得到完整的树。具体实现中采用递归的方法，递归的最大栈深度为n，在递归中有一步需要循环来查找头节点，平均时间复杂度为O(logn)，故该方法时间复杂度为O...

C++ 动态规划链表二叉树

2021-10-08

0 376