一、235. 二叉搜索树的最近公共祖先
题目链接:
学习前:
思路:
对于二叉搜索树,root不为空时与p和q的关系有4种,分别对应返回
- root<p && root<q----递归调用右孩子
- rootp || rootq----return root
- root在p、q之间----return root
- root>p && root>q----递归调用左孩子
2和3可以合并,采用中序遍历,实现递归和迭代的方式
学习后:
加深理解
二、701.二叉搜索树中的插入操作
题目链接:
学习前:
思路:
找到空结点,然后插入
- 当该节点是空结点时,返回目标值的新结点
- 当该节点值大于目标值,若左孩子不为空,递归调用左孩子;若左孩子为空,构造新节点并赋值给左孩子
- 当该节点值小于目标值,若右孩子不为空,递归调用右孩子;若右孩子为空,构造新节点并赋值给右孩子
学习后:
进一步优化。直接利用函数的返回值,当该节点值大于目标值,递归调用传入该结点的左孩子,右孩子同理
三、450.删除二叉搜索树中的节点
题目链接:
学习前:
思路:
难点在于找到的节点的左右孩子均不为空,思路是将该节点右孩子的最左孩子节点替换成该节点,但操作起来有点困难
学习后:
- 当找到节点的左右孩子均不为空时,将左子树直接作为右孩子最左孩子结点的左子树
- 学习前的思路是针对普通二叉树的思想,对于二叉搜索树,可以利用其特性简化操作
四、学习总结
- 时间:2.5h
- 二叉搜索树的特性,可以从根节点往叶子节点遍历,根据节点值可以只遍历左子树或右子树