基础 - 树 - 《算法》

什么是树
常用操作

什么是树

它是一种分层数据的抽象模型。前端中常见的树包括：DOM，级联选择，树形控件等
JS中没有树结构，但是可以用Object和Array构建树。如下：

{
  label: 'aa',
  value: 'vv',
  children: [{
    label: 'bb',
    value: 'bb',
  }]  
}

常用操作

深度/广度优先遍历，先中后序遍历

深度遍历与广度优先遍历

深度优先遍历: 尽可能搜索树的分支

访问根节点
对根节点的children挨个进行深度优先遍历 ```javascript const tree ={ val: ‘a’, children: [{ val: ‘b’, },{ val: ‘c’, }] }

const dfs = (root) =>{ console.log(‘val’, root.val) root.children.forEach(item=>{ def(item) }) }


<a name="CeazY"></a>
#### 广度优先遍历：先访问离根节点最近的节点
![image.png](https://cdn.nlark.com/yuque/0/2022/png/266511/1646837959811-ad52e4b3-aff4-440c-904e-5991ec84abbb.png#clientId=udfd70cb2-5ca8-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=453&id=u48871a0a&margin=%5Bobject%20Object%5D&name=image.png&originHeight=906&originWidth=492&originalType=binary&ratio=1&rotation=0&showTitle=false&size=177441&status=done&style=none&taskId=uda731b25-e606-4fbb-9548-dadbb8fbe51&title=&width=246)
- 新建队列，把根节点入队
- 把队头出队并访问
- 把对头的children挨个入队
- 重复第二，第三步，知道队列为空
```javascript
const bfs =(root)=>{
  const q = [root]
  while(q.length > 0) {
   const n = q.shift()
   console.log('n', n.val)
   n.children.forEach(child=>{
     q.push(child)
   })
  }
}

二叉树的先中后序遍历(递归版)

树中每个节点最多只能有两个子节点

const binaryTree = {
  val: 1,
  left: {
    val: 2,
    left: null,
    right: null
  },
  right: {
    val: 3,
    left: null,
    right: null
  },
}

先序遍历

访问根节点
对根节点的左子树进行先序遍历
对根节点的右子树进行先序遍历

const preOrder = (root) =>{
    if(!root) return
    console.log(root.val)
    preOrder(root.left)
    preOrder(root.right)
}

中序遍历

对根节点的左子树进行中序遍历
访问根节点
对根节点的右子树进行中序遍历

const inOrder = (root) =>{
    if(!root) return
    inOrder(root.left)
    console.log(root.val)
    inOrder(root.right)
}

后序遍历

对根节点的左子树进行后序遍历
对根节点的右子树进行后序遍历
访问根节点

const postOrder = (root) =>{
    if(!root) return
    postOrder(root.left)
    postOrder(root.right)
    console.log(root.val)
}

二叉树最大深度(leetcode 104)

新建变量，记录最大深度
深度遍历二叉树，并记录每个节点层级，同时不断刷新最大深度这个变量

返回变量

/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
  let max = 0
  function dfs(data, level) {
      if(!data) return
      // 优化:判断是叶子节点
      if(!data.left && !data.right){
          max = Math.max(max, level)
      }
      dfs(data.left, level + 1)
      dfs(data.right, level + 1)
  }
  dfs(root, 1)
  return max
};

二叉树最小深度(leetcode 111)

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(!root) return 0;
    const stack = [[root, 1]]
    while(stack.length){
        const [n, l] = stack.shift()
        if(!n.left && !n.right){
            return l
        }
        n.left && stack.push([n.left, l+1])
        n.right && stack.push([n.right, l+1])
    }
};

二叉树层序遍历（leetcode 102）

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root || root.length === 0) return []
    const stack = [[root, 0]]
    const res = []
    while(stack.length){
        const [n, level] = stack.shift()
        res[level] = res[level] || []
        res[level].push(n.val)
        n.left && stack.push([n.left, level+1])
        n.right && stack.push([n.right, level+1])
    }
    return res
};