知识点
LeetCode算法
LeetCode算法
复习
701.【二叉搜索树中的插入操作】
解题思路:
先找到位置,然后创建一个新节点,连接到原有的节点上。
还是利用递归的思路,但是因为需要新节点的创建,因此递归的返回值应该为TreeNode类型。
450.【删除二叉搜索树中的节点】
解题思路:
类似于插入操作,需要先找到位置,然后对二叉搜索树节点进行删除,并重组二叉搜索树。因此,首先明白递归函数的返回值应该为TreeNode类型。
关键的点就是如何进行删除。有三种情况:
1、刚好待删除节点为根节点,直接然后返回null即可。
2、只有左节点或者右节点,直接返回左节点或者右节点即可。
3、有左节点也有右节点。为了不破坏二叉搜索树的性质,我们需要从右子树中,寻找最小的节点,进行值替换,然后删除右子树中的最小节点,这里的删除可以直接使用当前的递归函数,因为当前函数的作用就是从一个二叉搜索树中删除一个节点。