[TOC]

前端工作中常見的樹包括：DOM樹、級聯(lián)選擇履婉、樹形控件...

JS中沒有樹結(jié)構(gòu)數(shù)據(jù)煤篙，但可以用Object和Array來構(gòu)建樹。

{
  value:"a",
  label:"",
  children:[
    {
      value:"b",
        label:"",
      children:[
         {
          value:"d",
          label:"",
          children:[],
        }
      ],
    },
     {
      value:"c",
        label:"",
      children:[
        {
        value:"e",
        label:"",
        children:[],
      },
      {
        value:"f",
        label:"",
        children:[],
      }
      ],
    },
  ]
}

    a
   / \
  b     c
  |  /  \
  d  e   f

樹常見的操作

• 深度/廣度優(yōu)先遍歷
• 先中后序遍歷

深度優(yōu)先遍歷算法

1. 先訪問根節(jié)點(diǎn)
2. 對根節(jié)點(diǎn)的children挨個進(jìn)行深度優(yōu)先遍歷

上圖執(zhí)行的順序是:a-b-d-c-e-f

// 參數(shù)root就是上面定義的數(shù)結(jié)構(gòu)
const dfs = (root) =>{
  console.log(root.value)
  root.children.forEach(child=>dfs(child))
}

廣度優(yōu)先遍歷算法

1. 新建一個隊列毁腿，把根節(jié)點(diǎn)入隊
2. 把隊頭出隊并訪問
3. 把隊頭的children挨個入隊
4. 重復(fù)2辑奈、3直至隊列為空

const bfs = (root) =>{
  const q = [root]
  while(q.length>0){
    const n =q.shift()
    console.log(n.value)
    n.children.forEach(child=>q.push(child))
  }
}

上圖執(zhí)行的順序是:a-b-c-d-e-f

什么是二叉樹

• 樹中每個節(jié)點(diǎn)最多只能有兩個子節(jié)點(diǎn)
• 在JS中通常用Object來模擬二叉樹

const tree = {
  value:'a',
  left:{
    value:'b',
    left:{
      value:'d',
      left:null,
      right:null,
    },
    right:{
      value:'e',
      left:null,
      right:null,
    },
  },
  right:{
    value:'c',
    left:{
      value:'f',
      left:null,
      right:null,
    },
    right:{
      value:'g',
      left:null,
      right:null,
    },
  },
}

先序遍歷算法(根-左-右)

1. 訪問根節(jié)點(diǎn)
2. 對根節(jié)點(diǎn)的左子樹進(jìn)行先序遍歷
3. 對根節(jié)點(diǎn)的右子樹進(jìn)行先序遍歷

// 遞歸版
const preorder=(root)=>{
  if(!root) return
  console.log(root.value)
  preorder(root.left)
  preorder(root.right)
}

// 非遞歸版
const preorder=(root)=>{
  if(!root) return
    const stack = [root]
  while(stack.length){
    const n = stack.pop()
    console.log(n.value)
    // 棧是后進(jìn)先出結(jié)構(gòu)，要先訪問left要最后入棧
    if(n.right) stack.push(n.right)
    if(n.left) stack.push(n.left)
  }
}

中序遍歷算法(左-根-右)

1. 對根節(jié)點(diǎn)的左子樹進(jìn)行中序遍歷
2. 訪問根節(jié)點(diǎn)
3. 對根節(jié)點(diǎn)的右子樹進(jìn)行中序遍歷

// 遞歸版
const inorder=(root)=>{
  if(!root) return
  inorder(root.left)
  console.log(root.value)
  inorder(root.right)
}

// 非遞歸版
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.value)
    p = n.right
  }
}

后序遍歷算法(左-右-根)

1. 對根節(jié)點(diǎn)的左子樹進(jìn)行后序遍歷
2. 對根節(jié)點(diǎn)的右子樹進(jìn)行后序遍歷
3. 訪問根節(jié)點(diǎn)

// 遞歸版
const postorder=(root)=>{
  if(!root) return
  postorder(root.left)
  postorder(root.right)
  console.log(root.value)
}

// 非遞歸版 - 利用先序的規(guī)則進(jìn)行倒序輸出
const postorder=(root)=>{
  if(!root) return
    const stack = [root]
  const outStack = []
  while(stack.length){
    const n = stack.pop()
    outStack.push(n)
    if(n.left) stack.push(n.left)
    if(n.right) stack.push(n.right)
  }
  outStack.forEach(item=>console.log(item.value))
}

leetcode練習(xí)題解

深度優(yōu)先

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

https://leetcode-cn.com/problems/path-sum/

廣度優(yōu)先

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

層序遍歷=廣度

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

中序遍歷

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/