tree | 树

相同的树

LeetCode 100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

默认的每个 treeNode 节点

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

思路 深度优先遍历

相同的条件

1. 如果比较两个树节点的子节点都不存在的时候
2. 同时要满足已经比较过的值相等

不相同的条件

1. 只要两个 node 节点的值不相同即为不相等
2. 只有两棵树有一方为 null 即不相等

Q & A

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
  if(p === null && q === null) return true;
  if(p === null || q === null) return false;
  if(p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

自动补位推荐

标题 输入电话号码时自动推荐出下一位合法的数字集 描述信息 公司有10万名员工，每名员工都有一个座机号码。现在要在网页上实现一个“自动补位推荐” 的功能，问如何实现？

解释： “自动补位推荐” 功能：有一个输入框，用户每输入一个数字，立马推荐出下一位合法的数字集合。 比如只有 5789234、5623786、5633678三个电话号码，当第一位输入5时，立马推荐下一位有效数字集合[ 7, 6 ]， 如果第二位输入6时，下一位有效数字集合为[2，3]....

方法1

构建字典树

const Trie = function () {
  this.children = {}
}

Trie.prototype.setup = function (phones) {
  for (const phone of phones) this.insert(phone)
}

Trie.prototype.insert = function (phone) {
  let node = this.children
  for (const n of phone) {
    node[n] || (node[n] = {})
    node = node[n]
  }
  node.isEnd = true
}

Trie.prototype.searchWithSuggestion = function (prefix) {
  let node = this.children
  for (const n of prefix) {
    if (!node[n]) return false
    node = node[n]
  }
  return Reflect.ownKeys(node)
}

var trie = new Trie()
trie.setup(['5789234', '5623786', '5633678'])

console.log(trie.searchWithSuggestion('56')) // [2,3]

方法2

通过 set

function suggestion(index, phones) {
  let i = 0, len = phones.length
  const set = new Set()
  while (i < len) (set.add(phones[i][index]), i ++)
  return [...set]
}