树

一种分层数据的抽象模型。前端常见的比如：dom树 级联选择 数形控件。前端可以用Object和Array模拟树

const tree = {
  value: 'root-node',
  label: 'root-node',
  childen: [
    {
      value: 'node1',
      label: 'node1',
      childen: [
        {
          value: 'node1-1',
          label: 'node1-1'
        }
      ]
    },
    {
      value: 'node2',
      label: 'node2',
      childen: []
    },
    {
      value: 'node3',
      label: 'node3',
      childen: []
    }
  ]
}

树的深度优先遍历

尽可能深的搜索树的分支

// 测试数据以上面为准
function dfs (root) {
  console.log('node: ', root.value);
  if (root.children && root.children.length) {
    root.children.forEach(element => dfs(element))
  }
}

树的广度优先遍历

尽可能的广搜索树分支

// 测试数据以上面为准
function bfs (root) {
  let q = [root]
  while (q.length > 0) {
    const n = q.shift()
    console.log('node: ', n.value);
    if (n.children && n.children.length) {
      n.children.forEach(element => {
        q.push(element)
      })
    }
  }
}

二叉树的前序遍历

二叉树是节点只有两个子节点，下面用js模拟二叉树

const tree = {
  value: 1,
  left: {
    value: 2,
    left: null,
    right: null
  },
  right: {
    value: 3,
    left: null,
    right: null
  }
}

前序遍历顺序是：

1. 根节点
2. 左节点
3. 右节点

function fun1 (tree) {
  if (!tree) return;
  console.log('node: ', tree.value);
  fun1(tree.left)
  fun1(tree.right)
}

二叉树的中序遍历

前序遍历顺序是：

1. 左节点
2. 根节点
3. 右节点

function fun2 (tree) {
  if (!tree) return;
  fun2(tree.left)
  console.log('node: ', tree.value);
  fun2(tree.right)
}

二叉树的后序遍历

前序遍历顺序是：

1. 左节点
2. 右节点
3. 根节点

function fun3 (tree) {
  if (!tree) return;
  fun3(tree.left)
  fun3(tree.right)
  console.log('node: ', tree.value);
}

相关leetcode题：

• 二叉树的最大深度
• 二叉树的最小深度
• 二叉树的层序遍历
• 二叉树的中序遍历
• 路径总和