文和906

题解

未归档(4) 项目笔记(5)

/ 注册

全部文章 / 题解（共103篇）

题解 | #对称的二叉树#

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

C++ 二叉树

2021-10-11

0 411

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

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

C++ 二叉树递归

2021-10-09

0 373

题解 | #平衡二叉树#

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

C++ 二叉树

2021-10-09

0 385

题解 | #二叉搜索树与双向链表#

观察容易发现双向链表的顺序与该二叉树中序遍历的结果相同。故首先考虑中序遍历解题。最开始由于题目中要求空间复杂度为O(1)，故考虑原地操作，但递归的中序遍历也需要用到递归栈，如果真的要满足空间复杂度为O(1)，则需要考虑迭代中序遍历树，或放弃中序遍历的思路。这里最终还是选择使用中序遍历，将结点按中...

C++ 二叉搜索树

2021-10-09

0 419

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

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

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

2021-10-09

0 362

题解 | #二叉搜索树的后序遍历序列#

刚看到题目尝试使用迭代的方法来找规律逐个元素判断，写到后面发现情况太过复杂，还是递归来的方便。总体思路是后序遍历的搜索树，其最后一个结点为头结点，而前面的数列则可根据该头结点分为连续的两部分，一部分笔比该结点大，一部分比该结点小。这样就得到了基本的拆分思路，每次都找到数列最后一个数，然后找到数列...

C++ 二叉搜索树递归

2021-10-09

0 359

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

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

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

2021-10-08

0 408

题解 | #二叉树的镜像#

开始看到题目中说有原地算法，想挑战一下的，但是想了一会没什么思路，还是用常规的遍历解法来做了。逻辑十分简单，遍历头结点，交换左右子树，再依次遍历左右子树，直到遍历所有结点。使用递归进行遍历，时间复杂度为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