文和906

题解

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

/ 注册

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

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

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

C++ 二叉搜索树

2021-10-09

0 419

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

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

C++ 二叉搜索树递归

2021-10-09

0 359

题解 | #二叉搜索树的第k个结点#

由于是二叉搜索树，所以一个结点左边的数都比该结点小，右边的数都比该结点大。所以可以通过递归，按照中序遍历的顺序，先找到最左边的结点，该结点即为最小结点。然后开始计数，遍历到的第k个结点即为第k小结点。这样做仅递归遍历了一次链表，大部分情况是不用遍历整个链表的，所以时间复杂度小于等于O(n)。递归...

C++ 二叉搜索树链表

2021-09-30

0 410