011.修改二叉搜索树

• 701.二叉搜索树中的插入操作
• 450.删除二叉搜索树中的节点
  • 迭代
  • 递归
• 669.修剪二叉搜索树
  • 递归
  • 迭代

修剪二叉搜索树 - 递归 §

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func trimBST(root *TreeNode, low int, high int) *TreeNode {
	if root == nil {
		return nil
	}
 
	val := root.Val
	if val < low {
		return trimBST(root.Right, low, high)
	}
 
	if val > high {
		return trimBST(root.Left, low, high)
	}
 
	root.Left = trimBST(root.Left, low, high)
	root.Right = trimBST(root.Right, low, high)
 
	return root
}

修剪二叉搜索树 - 迭代 §

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type Item struct {
	Cur *TreeNode
	Prev *TreeNode
	IsLeft bool
}
 
func trimBST(root *TreeNode, low int, high int) *TreeNode {
	for root != nil && (root.Val < low || root.Val > high) {
		if root.Val < low {
			root = root.Right
		} else {
			root = root.Left
		}
	}
	cur := root
	for cur != nil {
		for cur.Left != nil && cur.Left.Val < low {
			cur.Left = cur.Left.Right
		}
		cur = cur.Left
	}
	cur = root
	for cur != nil {
		for cur.Right != nil && cur.Right.Val > high {
			cur.Right = cur.Right.Left
		}
		cur = cur.Right
	}
 
	return root
}