数据结构的故事之二叉树, 前缀树, N叉树

二叉树

深度优先遍历 前序遍历

``````
var preorderTraversal = function (root) {
let result = []

const traversing = (node) => {
// 结束递归
if (!node) return []

// 首先遍历当前的节点
result.push(node.val)
// 如果有左子树优先遍历左子树
if (node.left) {
result.concat(traversing(node.left))
}
// 遍历又子树
if (node.right) {
result.concat(traversing(node.right))
}
}

traversing(root)

return result
}``````

深度优先遍历 中序遍历

``````
var inorderTraversal = function (root) {
let result = []
const traversing = (node) => {
if (!node) return
// 优先遍历左子树
if (node.left) {
traversing(node.left)
}
// 然后获取当前的节点
if (node.val) {
result.push(node.val)
}
// 然后遍历右子树
if (node.right) {
traversing(node.right)
}
}
traversing(root)
return result
}``````

深度优先遍历 后序遍历

``````
var postorderTraversal = function (root) {
let result = []
const traversing = (node) => {
if (!node) return
if (node.left) {
traversing(node.left)
}
if (node.right) {
traversing(node.right)
}
if (node.val) {
result.push(node.val)
}
}
traversing(root)
return result
};``````

广度优先遍历

``````
var levelOrder = function (root) {
let result = []

const traversing = (node, level) => {
if (!node) return
if (!result[level]) result[level] = []
result[level].push(node.val)
if (node.left) {
traversing(node.left, level + 1)
}
if (node.right) {
traversing(node.right, level + 1)
}
}

traversing(root, 0)
return result
}``````

二叉树的最大深度

解答

``````
var maxDepth = function(root) {
if (!root) return 0

const traversing = (node) => {
if (!node) return

if (!node.left && !node.right) {
node.depth = 1
return
}
if (node.left) {
traversing(node.left)
}
if (node.right) {
traversing(node.right)
}
let max_left_depth = 0
let max_right_depth = 0

if (node.left) {
max_left_depth = node.left.depth
}
if (node.right) {
max_right_depth = node.right.depth
}

node.depth = Math.max(max_left_depth, max_right_depth) + 1
}

traversing(root)

return root.depth
}``````

对称二叉树

``````// 对称二叉树
1
/ \
2   2
/ \ / \
3  4 4  3

// 不是对称二叉树
1
/ \
2   2
\   \
3    3``````

解答

``````
var isSymmetric = function(root) {
// BFS遍历
let result = []
const traversing = (node, level) => {

if (!result[level]) result[level] = []

// 不存在的节点使用null填充
if (!node) {
// 终止递归
return result[level].push('null')
} else {
result[level].push(node.val)
}

if (node.left) {
traversing(node.left, level + 1)
} else {
traversing(null, level + 1)
}

if (node.right) {
traversing(node.right, level + 1)
} else {
traversing(null, level + 1)
}

}

traversing(root, 0)

// 判断每一级的结果能否构成回文字符串
for (let i = 0; i < result.length - 1; i++) {
if (result[i].join('') !== result[i].reverse().join('')) {
return false
}
}
return true
};``````

路径总和

题目

``````// 给定目标sum = 22
// 5->4->11->2和为22, 返回true

5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1``````

解答

``````
var hasPathSum = function(root, sum) {
let result = []
const traversing = (root, sum) => {

if (!root) return false

// 说明拥有路径等于目标的和
if (!root.left && !root.right && root.val === sum) {
result.push(root.val)
}

if (root.left) {
traversing(root.left, sum - root.val)
}

if (root.right) {
traversing(root.right, sum - root.val)
}
}

traversing(root, sum)

return result.length > 0
};``````

从中序与后序遍历序列构造二叉树

题目

``````
// 中序遍历 inorder = [9,3,15,20,7]
// 后序遍历 postorder = [9,15,7,20,3]

// 构建结果
3
/ \
9  20
/  \
15   7``````

解答

``````
var buildTree = function(inorder, postorder) {
let binaryTree = {}

const iteration = (postorder, inorder, tree) => {

if (!postorder.length) {
binaryTree = null
return
}

tree.val = null
tree.left = {
val: null,
left: null,
right: null
}
tree.right = {
val: null,
left: null,
right: null
}

// 前序遍历第一个节点为当前树的根节点
let rootVal = postorder.splice(postorder.length - 1, 1)[0]
// 中序遍历根节点的索引
let rootIndex = inorder.indexOf(rootVal)
// 中序遍历的左子树
let inorderLeftTree = inorder.slice(0, rootIndex)
// 中序遍历的右子树
let inorderRightTree = inorder.slice(rootIndex + 1)
// 前序遍历的左子树
let postorderLeftTree = postorder.slice(0, inorderLeftTree.length)
// 前序遍历的右子树
let postorderRightTree = postorder.slice(inorderLeftTree.length)

tree.val = rootVal

if (postorderLeftTree.length === 1 || inorderLeftTree.length === 1) {
tree.left.val = postorderLeftTree[0]
} else if (postorderLeftTree.length > 1 || inorderLeftTree.length > 1) {
iteration(postorderLeftTree, inorderLeftTree, tree.left)
} else {
tree.left = null
}

if (postorderRightTree.length === 1 || inorderRightTree.length === 1) {
tree.right.val = postorderRightTree[0]
} else if (postorderRightTree.length > 1 || inorderRightTree.length > 1) {
iteration(postorderRightTree, inorderRightTree, tree.right)
} else {
tree.right = null
}
}

iteration(postorder, inorder, binaryTree)

return binaryTree
}``````

从前序与中序遍历序列构造二叉树

解答

``````
var buildTree = function(preorder, inorder) {

let binaryTree = {}

const iteration = (preorder, inorder, tree) => {

if (!preorder.length) {
binaryTree = null
return
}

tree.val = null
tree.left = {
val: null,
left: null,
right: null
}
tree.right = {
val: null,
left: null,
right: null
}

// 前序遍历第一个节点为当前树的根节点
let rootVal = preorder.splice(0, 1)[0]
// 中序遍历根节点的索引
let rootIndex = inorder.indexOf(rootVal)
// 中序遍历的左子树
let inorderLeftTree = inorder.slice(0, rootIndex)
// 中序遍历的右子树
let inorderRightTree = inorder.slice(rootIndex + 1)
// 前序遍历的左子树
let preorderLeftTree = preorder.slice(0, inorderLeftTree.length)
// 前序遍历的右子树
let preorderRightTree = preorder.slice(inorderLeftTree.length)

tree.val = rootVal

if (preorderLeftTree.length === 1 || inorderLeftTree.length === 1) {
tree.left.val = preorderLeftTree[0]
} else if (preorderLeftTree.length > 1 || inorderLeftTree.length > 1) {
iteration(preorderLeftTree, inorderLeftTree, tree.left)
} else {
tree.left = null
}

if (preorderRightTree.length === 1 || inorderRightTree.length === 1) {
tree.right.val = preorderRightTree[0]
} else if (preorderRightTree.length > 1 || inorderRightTree.length > 1) {
iteration(preorderRightTree, inorderRightTree, tree.right)
} else {
tree.right = null
}
}

iteration(preorder, inorder, binaryTree)

return binaryTree
}``````

二叉搜索树

验证二叉搜索树

解答

``````
var isValidBST = function(root) {
if (!root) return true

// 中序DFS
let result = []

const iteration = (root) => {
if (root.left) {
iteration(root.left)
}
result.push(root.val)
if (root.right) {
iteration(root.right)
}
}
iteration(root)
let resultString = result.join(',')
let result2String = [...new Set(result.sort((a, b) => a - b))].join(',')
return resultString === result2String
};``````

在二叉搜索树中实现搜索操作

``````// 递归就完事了
var searchBST = function(root, val) {
if (!root) return null

let result = null

const seatch = (node) => {
if (node.val === val) {
return result = node
} else if (val > node.val && node.right) {
seatch(node.right)
} else if (val < node.val && node.left) {
seatch(node.left)
}
}

seatch(root)

return result
};``````

在二叉搜索树中实现插入操作

``````
var insertIntoBST = function(root, val) {
const insert = (root) => {
if (val > root.val) {
if (root.right) {
insert(root.right)
} else {
root.right = new TreeNode(val)
}
} else if (val < root.val) {
if (root.left) {
insert(root.left)
} else {
root.left = new TreeNode(val)
}
}
}

insert(root)

return root
};``````

在二叉搜索树中实现删除操作

``````
/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
var deleteNode = function(root, key) {

// 根节点为空的情况
if (!root) {
return null
}

if (!root.left && !root.right && root.val === key) {
root = null
return root
}

if (!root.left && root.right && root.val === key) {
root = root.right
return root
}

if (root.left && !root.right && root.val === key) {
root = root.left
return root
}

// 根节点替换的情况

// 寻找当前树的最小节点
const findMin = (root) => {
let min = root
while (min.left) {
min = min.left
}
return min
}

let parentNode = null

// 找到最近的父级
const searchParent = (node, searchValue) => {
console.log('???')
let current = node
let breaker = false

while (!breaker) {
console.log('查找父亲')
if (
(current.left && searchValue === current.left.val) ||
(current.right && searchValue === current.right.val)
) {
breaker = true
} else if (searchValue < current.val) {
current = current.left
} else if (searchValue > current.val) {
current = current.right
} else {
current = null
}

if (!current) break
}

parentNode = current
}

const remove = (node, deleteValue) => {
if (node.val === deleteValue) {
console.log('1')
// node为要删除的节点
if (!node.left && !node.right) {
console.log('3')
// 如果没有任何子节点
searchParent(root, node.val)
if (parentNode.left && parentNode.left.val === deleteValue) {
parentNode.left = null
} else {
parentNode.right = null
}
} else if (!node.left && node.right) {
console.log('4')
// 如果只有一个子节点
searchParent(root, node.val)
if (parentNode.left && parentNode.left.val === deleteValue) {
parentNode.left = node.right
} else {
parentNode.right = node.right
}
} else if (node.left && !node.right) {
console.log('5')
// 如果只有一个子节点
searchParent(root, node.val)
if (parentNode.left && parentNode.left.val === deleteValue) {
parentNode.left = node.left
} else {
parentNode.right = node.left
}
} else {
console.log('6')
// 如果有两个子节点
// 找到右子树中最小的节点
let minNode = findMin(node.right)
console.log('7')
let minNodeValue = minNode.val
console.log('8')
remove(root, minNodeValue)
console.log('9')
node.val = minNodeValue
console.log('10')
}
} else if (deleteValue > node.val && node.right) {
console.log('2')
remove(node.right, deleteValue)
} else if (deleteValue < node.val && node.left) {
console.log('3')
remove(node.left, deleteValue)
}
}

remove(root, key)

return root
};``````

二叉搜索树的最近公共祖先

解答

``````
/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q)
}
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q)
}
return root
};``````

前缀树

实现 Trie (前缀树)

``````
var TrieNode = function (val = null) {
// 当前的值
this.val = val
// 当前节点的子节点
this.children = {}
// 表示当前节点是否为一个单词
this.isWord = false
}

// 添加到节点
let child = new TrieNode(val)
this.children[val] = child
return this.children[val]
}

// 判断是否包含子节点
TrieNode.prototype.has = function (val) {
return this.children[val] ? true : false
}

/**
* Initialize your data structure here.
*/
var Trie = function() {
// 初始化根节点
this.root = new TrieNode('')
};

/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let current = this.root
let words = word.split('')
let i = 0
// 替换最后一个节点
while (i < words.length) {
if (!current.has(words[i])) {
// 如果不存在该子节点
} else {
// 如果存在该子节点
current = current.children[words[i]]
}
i += 1
}
current.isWord = true
};

/**
* Returns if the word is in the trie.
* 判断是否存在单词
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let current = this.root
let words = word.split('')
let i = 0
let result = null
while (i < words.length) {
if (current.has(words[i])) {
current = current.children[words[i]]
i += 1
} else {
return false
}
}
return current.isWord

};

/**
* Returns if there is any word in the trie that starts with the given prefix.
* 判断是否包含单词
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let current = this.root
let prefixs = prefix.split('')
let i = 0
while (i < prefixs.length) {
if (current.has(prefixs[i])) {
current = current.children[prefixs[i]]
i += 1
} else {
return false
}
}
return true
};

/**
* Your Trie object will be instantiated and called as such:
* var obj = Object.create(Trie).createNew()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/``````

单词替换

sentence(句子) = "the cattle was rattled by the battery"

解答

``````
var replaceWords = function(dict, sentence) {
let sentences = sentence.split(' ')
let result = []

for (let i = 0; i < sentences.length; i++) {
let trie = new Trie()
// 句子中的每一个词形成一个前缀树
trie.insert(sentences[i])
let min = sentences[i]
for (let j = 0; j < dict.length; j++) {
// 判断是否包含词根
if (trie.startsWith(dict[j])) {
// 取最短的词根
min = min.length < dict[j].length ? min : dict[j]
}
}
result.push(min)
}

return result.join(' ')
};``````

N叉树

N叉树的前序遍历

``````
var preorder = function(root) {

let result = []

const iteration = (root) => {
if (!root) return

result.push(root.val)

if (root.children) {
for (let i = 0; i < root.children.length; i++) {
iteration(root.children[i])
}
}
}

iteration(root)

return result
}``````

N叉树的后序遍历

``````
var postorder = function(root) {
let result = []

const iteration = (root) => {
if (!root) return

if (root.children) {
for (let i = 0; i < root.children.length; i++) {
iteration(root.children[i])
}
}

result.push(root.val)
}

iteration(root)

return result
};``````

N叉树的层序遍历

``````
var levelOrder = function (root) {
let reuslt = []

const iteration = (root, level) => {
if (!root) return

if (!reuslt[level]) {
reuslt[level] = []
}

reuslt[level].push(root.val)

for (let i = 0; i < root.children.length; i++) {
iteration(root.children[i], level + 1)
}
}

iteration(root, 0)

return reuslt
};``````

N叉树最大深度

解答

``````
var maxDepth = function(root) {
let reuslt = []

const iteration = (root, level) => {
if (!root) return

if (!reuslt[level]) {
reuslt[level] = []
}

reuslt[level].push(root.val)

for (let i = 0; i < root.children.length; i++) {
iteration(root.children[i], level + 1)
}

}

iteration(root, 0)

return reuslt.length
};``````