摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #二叉搜索树的最近公共祖先# 来自专栏

题目的主要信息：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先：对于该题的最近的公共祖先定义：对于有根树T的两个结点p、q，最近公共祖先LCA(T,p,q)表示一个结点x，满足x是p和q的祖先且x的深度尽可能大一个节点也可以是它自己的祖先二叉搜索树是若它的左子树不空，则左子树上...

C++ 二叉搜索树递归

2021-11-30

0 528

题解 | #二叉搜索树的第k个结点# 来自专栏

思路：根据二叉搜索树的性质，其中序遍历是由大到小的，由此仅需要中序遍历找到第k个小的结点即可。中序遍历有两种方式。方法一：递归中序遍历具体做法：另写一函数进行递归中序遍历，设置全局变量count记录遍历了多少个结点，res记录第k个结点。 class Solution { public:...

二叉搜索树递归中序遍历非递归排序

2021-07-15

4 676

题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树# 来自专栏

思路：关于搜索二叉树的知识：搜索二叉树左子树上所有值小于根节点，右子树上所有值大于根节点，中序遍历后得到的是一个递增序列。关于完全二叉树的知识：完全二叉树叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树，出现叶子节点以后的节点都是叶子。由此，可用二叉树...

二叉搜索树完全二叉树中序遍历层次遍历队列递归栈

2021-07-14

4 958

题解 | #二叉搜索树与双向链表# 来自专栏

思路：题目中所给的关键信息：这是一颗二叉搜索树，中序遍历便是从小到大的排序不能添加新的结点，要在原结点基础上添加链表链接 *故采用二叉树中序遍历法遍历全树，依次添加链接，创建两个指针，一个指向题目中要求的链表头（head），一个指向当前遍历的前一结点（pre)。方法一：递归中序遍历具体...

二叉搜索树双向链表中序遍历递归非递归

2021-07-13

0 784