脚本宝典收集整理的这篇文章主要介绍了⑧ 数据结构之“树”,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
const tree = {
val: 'a',
children: [{
val: 'b',
children: [{
val: 'd',
children: [],
},{
val: 'e',
children: [],
}],
},{
val: 'c',
children: [{
val: 'f',
children: [],
},{
val: 'g',
children: [],
}],
}],
}
// dfs
const DFS = root => {
console.log(root.val)
root.chileren.forEach(child => DFS(child))
// abdecfg
// bfs
const BFS = root => {
const q = [root]
while(q.length) {
const n = q.shift()
console.log(n.val)
n.children.forEach(child => q.push(child))
}
}
// abcdefg
// bt
const bt = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null
},
right: {
val: 5,
left: null,
right: null
}
},
right: {
val: 3,
left: {
val: 6,
left: null,
right: null
},
right: {
val: 7,
left: null,
right: null
}
}
}
// preorder
const preorder = root => {
if(!root) return
console.log(root.val)
preorder(root.left)
preorder(root.right)
}
// inorder
const inorder = root => {
if(!root) return
inorder(root.left)
console.log(root.val)
inorder(root.right)
}
// postorder
const postorder = root => {
if(!root) return
postorder(root.left)
postorder(root.right)
console.log(root.val)
}
// preorder
const preorder = root => {
if(!root) return
const stack = [root]
while(stack.length) {
const n = stack.pop()
console.log(n.val)
if(n.right) stack.push(n.right)
if(n.left) stack.push(n.left)
}
}
// inorder
const inorder = root => {
if(!root) return
const stack = []
let p = root
while(stack.length || p) {
while(p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
console.log(n.val)
p = n.right
}
}
// postorder
const postorder = root => {
if(!root) return
const stack = [root]
const outputStack = []
while(stack.length) {
const n = stack.pop()
outputStack.push(n)
if(n.left) stack.push(n.left)
if(n.right) stack.push(n.right)
}
while(outputStack.length) {
const n = outputStack.pop()
console.log(n.val)
}
}
function maxDepth(root) {
let res = 0
const dfs = (n, l) => {
if(!n) return
if(!n.left && !n.right) {
res = Math.max(res, l)
}
dfs(n.left, l+1)
dfs(n.right, l+1)
}
dfs(root, 1)
return res
}
function minDepth(root) {
if(!root) return 0
const q = [[root, 1]]
while(q.length) {
const [n, l] = q.shift()
if(!n.left && !n.right) {
return l
}
if(n.left) q.push([n.left, l+1])
if(n.right) q.push([n.right, l+1])
}
}
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
function levelOrder(root) {
if(!root) return []
const q = [[root, 0]]
const res = []
while(q.length) {
const [n, level] = q.shift()
if(!res[level]) {
res.push([n.val])
} else {
res[level].push(n.val)
}
if(n.left) q.push([n.left, level+1])
if(n.right) q.push([n.right, level+1])
}
return res
}
function levelOrder(root) {
if(!root) return []
const q = [root]
const res = []
while(q.length) {
let len = q.length
res.push([])
while(len--) {
const n = q.shift()
res[res.length-1].push(n.val)
if(n.left) q.push(n.left)
if(n.right) q.push(n.right)
}
}
return res
}
function inorderTraversal(root) {
const res = []
const rec = n => {
if(!n) return
rec(n.left)
res.push(n.val)
rec(n.right)
}
rec(root)
return res
}
function inorderTraversal(root) {
const res = []
const stack = []
let p = root
while(stack.length || p) {
while(p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
res.push(n.val)
p = n.right
}
return res
}
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出:true
function hasPathSum(root, sum) {
if(!root) return false
let res = false
const dfs = (n, s) => {
if(!n.left && !n.right && s === sum) {
res = true
}
if(n.left) dfs(n.left, s + n.left.val)
if(n.right) dfs(n.right, s + n.right.val)
}
dfs(root, root.val)
return res
}
function levelOrder(root) {
if(!root) return []
const q = [root]
const res = []
while(q.length) {
let len = q.length
res.push([])
while(len--) {
const n = q.shift()
res[res.length-1].push(n.val)
if(n.left) q.push(n.left)
if(n.right) q.push(n.right)
}
}
return res
}
const json = {
a: { b: { c: 1 } },
d: [1, 2]
}
const dfs = (n, path) => {
console.log(n, path)
Object.keys(n).forEach(k => {
dfs(n[k], path.concat(k))
})
}
以上是脚本宝典为你收集整理的⑧ 数据结构之“树”全部内容,希望文章能够帮你解决⑧ 数据结构之“树”所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。