LeetCode75学习计划-二叉搜索树/前缀树

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为二叉搜索树/前缀树。

二叉搜索树中的搜索

题目标签：

• 树
• 二叉搜索树

题目难度： Easy

题目描述：

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

解题思路：

• 依据二叉搜索树的特性，递归查找子树即可

代码实现：

func searchBST(root *TreeNode, val int) *TreeNode {
  // 为空返回空节点
  if root == nil {
    return nil
  }
  // 找到了则返回以当前节点为根节点的子树
  if val == root.Val {
    return root
  }
  // 如果val小于root.Val，那么肯定在左子树中，否则在右子树中
  if val < root.Val {
    return searchBST(root.Left, val)
  }
  return searchBST(root.Right, val)
}

删除二叉搜索树中的节点

题目标签：

• 树
• 二叉搜索树

题目难度： Medium

题目描述：

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

• 首先找到需要删除的节点；
• 如果找到了，删除它。

解题思路：

• 通过递归的方式来解决
• 如果 root 为空则返回空，如果 root.Val > key ， 则递归 root.Left,否则递归 root.Right
• 如果 root.Val = key， root 就是要删除的节点。此时要删除 root 并将他的子树合并成一颗新的树
  • 如果 root 是叶子节点，可以直接删除
  • 如果 root 只有左子树或右子树，可以将左/右子树作为新的子树。
  • 如果 root 有左右子树，那么就要找 root 的右子树中的最小节点作为新的根节点

代码实现：

func deleteNode(root *TreeNode, key int) *TreeNode {
  switch {
  case root == nil:
    return nil
  case root.Val > key:
    root.Left = deleteNode(root.Left, key)
  case root.Val < key:
    root.Right = deleteNode(root.Right, key)
  case root.Left == nil || root.Right == nil:
    if root.Left != nil {
      return root.Left
    }
    return root.Right
  default:
    // 寻找右子树的最小节点
    successor := root.Right
    for successor.Left != nil {
      successor = successor.Left
    }
    // 将这个节点作为新的树根节点后从原来的位置删除
    successor.Right = deleteNode(root.Right, successor.Val)
    successor.Left = root.Left
    return successor
  }
  return root
}

实现前缀树

题目标签：

• 哈希表
• 字符串
• 字典树

题目难度： Medium

题目描述：

前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串word的前缀之一为 prefix ，返回 true ；否则，返回 false 。

解题思路：

代码实现：

type Trie struct {
  children [26]*Trie
  isEnd bool
}
func Constructor() Trie {
  return Trie{}
}

func (t *Trie) Insert(word string) {
  node := t
  for _, ch := range word {
    ch -= 'a'
    if node.children[ch] == nil {
      node.children[ch] = &Trie{}
    }
    node = node.children[ch]
  }
  node.isEnd = true
}

func (t *Trie) SearchPrefix(prefix string) *Trie {
  node := t
  for _, ch := range prefix {
    ch -= 'a'
    if node.children[ch] == nil {
      return nil
    }
    node = node.children[ch]
  }
  return node
}

func (t *Trie) Search(word string) bool {
  node := t.SearchPrefix(word)
  return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
  return t.SearchPrefix(prefix) != nil
}

推荐搜索系统

题目标签：

• 数组
• 字符串
• 字典树

题目难度： Medium

题目描述：

给你一个产品数组 products 和一个字符串 searchWord ，products 数组中每个产品都是一个字符串。

请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。

请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

解题思路：

• 没搞太清楚，有点迷糊，后续补吧，先抄个答案

代码实现：

type dirNode struct {
	child     [26]*dirNode
	indexList []int
}

func suggestedProducts(products []string, searchWord string) [][]string {
	var res [][]string
	sort.SliceStable(products, func(i, j int) bool {
		return products[i] < products[j]
	})
	var pro func(i, index int, d *dirNode)
	pro = func(i, index int, d *dirNode) {
		if i > 0 {
			d.indexList = append(d.indexList, index)
		}
		if i >= len(products[index]) {
			return
		}
		if d.child[products[index][i]-'a'] == nil {
			d.child[products[index][i]-'a'] = new(dirNode)
		}
		pro(i+1, index, d.child[products[index][i]-'a'])

	}
	dir := dirNode{}
	for i := 0; i < len(products); i++ {
		pro(0, i, &dir)
	}
	var sea func(i, max int, d *dirNode)
	sea = func(i, max int, d *dirNode) {
		var temp []string
		if i >= max {
			for j := 0; j < len(d.indexList) && j < 3; j++ {
				temp = append(temp, products[d.indexList[j]])
			}
			res = append(res, temp)
			return
		}
		if d.child[searchWord[i]-'a'] == nil {
			res = append(res, temp)
			return
		}
		sea(i+1, max, d.child[searchWord[i]-'a'])
	}

	for i := 0; i < len(searchWord); i++ {
		sea(0, i+1, &dir)
	}

	return res
}