Problem: 669. 修剪二叉搜索树

思路

这道题可以总结为两句话:

Problem: 450. 删除二叉搜索树中的节点

思路

本题如代码随想录所说,有以下五种情况：

Problem: 538. 把二叉搜索树转换为累加树

思路

根据实例可以看出,是根据右->中->左的顺序累加的,我们只需要得到前面一个节点,与当前节点相加即可,并且直接改变原值,进行累计。

复杂度

时间复杂度:

Problem: 108. 将有序数组转换为二叉搜索树

思路

与构造二叉树相似,我们需要找到中间节点,但是这是二叉搜索树,并且给定了一个升序数组,我们只需要找到升序数组中的中间节点便可以作为二叉树的中间节点。

递归得到左节点和右节点。

Problem: 198. 打家劫舍

Reference

https://www.programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html

思路

dp数组含义: 打劫到第i间的最大收益

Problem: 51. N 皇后

Reference

https://www.programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html

思路

使用回溯算法解题。

Problem: 235. 二叉搜索树的最近公共祖先

https://www.programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

本题与二叉树的最近公共祖先不同之出,就是本题是二叉搜索树,可以利用二叉搜索树的有序性,如果val同时大于p q那么往左搜索,如果val同时小于p q那么往右边搜索,其他情况就只能是在p q之间了,那么这个节点就是他的最大祖先,直接返回。

Problem: 236. 二叉树的最近公共祖先

[TOC]

思路

我们需要得到祖先节点,也就是说先遍历子节点再遍历父节点,后序遍历可以做到这一点,对于从子节点判断父节点的题目都可以用后序遍历。

Problem: 501. 二叉搜索树中的众数

Reference

https://www.programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

我们还是使用二叉搜索树的特性,中序遍历可以的到,有序的序列,于是我们使用中序遍历。

Problem: 530. 二叉搜索树的最小绝对差

Reference

https://www.programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

中序遍历,可以得到递增序列,求差值,最小绝对差值,相邻的元素差值最小。