一、530.二叉搜索树的最小绝对差
题目链接:
学习前:
思路:
中序遍历(递归+迭代)。首先中序遍历,将数值按照递增的方式存储,然后再计算最小绝对差
学习后:
中序遍历+双指针。在中序遍历中,一直存在指针指向前序结点,故在遍历过程中就可计算最小绝对差
二、501.二叉搜索树中的众数
题目链接:
学习前:
思路:
中序遍历(递归)。先中序遍历并将结果存放在map中,然后遍历map找到频率最高的,再遍历进行存放
学习后:
可以进一步优化,定义list代替map,定义pre作为前序结点
- 通过判断pre与cur是否相等来修改curCount的值
- 通过判断curCount与maxCount的大小来对list进行操作
- 最后的结果存放在list中且只需一次遍历
三、236. 二叉树的最近公共祖先
题目链接:
学习前:
思路:
没看视频前的思路不能处理自己本身就是最近公共祖先的情况
学习后:
后序遍历
-
方法参数:(TreeNode root, TreeNode p, TreeNode q)
-
返回类型:TreeNode
-
终止条件:这一点很关键
if(root==null || root==p || root==q) return root;
-
单层递归逻辑:
-
递归调用分别返回左孩子和右孩子
-
左孩子和右孩子的返回值均不为空则返回当前结点,有一个不为空则返回该孩子,其余的则返回空
-
四、学习总结
- 时间:3h
- 求公共祖先还需要再理解一下