450. Delete Node in a BST

Solution idea

Post-Order Traversal

• 难点: 分类讨论 所有可能遇到的删除节点的情况， 并保证所有情况下的操作都能保持BST特性
  • 情况一: 当前节点的左孩子为空, 直接返回右孩子
  • 情况二: 当前节点的右孩子为空, 直接返回左孩子
  • 情况三: 当前节点的左、右孩子都非空, 把左子树挂到右子树最左边的叶子节点下面

Time complexity = $O(n)$

Resource

有很好的图示：代码随想录-450.删除二叉搜索树中的节点