算法 - 树

树

• 一种分层数据的抽象模型
• 前端工作中常见的数包括：DOM树、级联选择、树形控件…
• javascript中没有树，但是可以用Object和Array构建树
• 树的常用操作：深度/广度优先遍历、先中后序遍历

树的深度与广度优先遍历

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

深度优先遍历
广度优先遍历：先访问离根节点最近的节点
广度优先遍历

深度优先遍历(dfs)算法口诀

• 访问根节点
• 对根节点的children挨个进行深度优先遍历

const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                { val: 'd', children: [] },
                { val: 'e', children: [] }
            ]
        }, {
            val: 'c',
            children: [
                { val: 'f', children: [] },
                { val: 'g', children: [] }
            ]
        }
    ]
}
const dfs = (root) => {
    console.log(root.val)
    root.children && root.children.forEach(dfs) // 防止初学者懵逼，相当于 root.children.forEach(child => dfs(child))
}

dfs(tree) // a b d e c f g

广度优先遍历(bfs)算法口诀

• 新建一个队列，把根节点入队
• 把队头出队并访问
• 把对头的children挨个入队
• 重复第二、三步，直到队列为空

const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                { val: 'd', children: [] },
                { val: 'e', children: [] }
            ]
        }, {
            val: 'c',
            children: [
                { val: 'f', children: [] },
                { val: 'g', children: [] }
            ]
        }
    ]
}
const bfs = (root) => {
    const q = [root]
    while (q.length > 0) {
        const n = q.shift()
        console.log(n.val)
        n.children.forEach(child => q.push(child))
    }
}

bfs(tree) // a b c d e f g

二叉树的先中后序遍历（递归实现）

二叉树

• 树中每个节点最多只能有两个子节点
• 在JS中通常使用Object来模拟二叉树

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)
}

preorder(bt) // 1 2 4 5 3 6 7

中序遍历(inorder)算法口诀

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

中序遍历

// bt同上，省略不写
const inorder = root => {
    if (!root) return
    inorder(root.left)
    console.log(root.val)
    inorder(root.right)
}

inorder(bt) // 4 2 5 1 6 3 7

后续遍历算法口诀

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

后续遍历

// bt同上，省略不写
const postorder = root => {
    if (!root) return
    postorder(root.left)
    postorder(root.right)
    console.log(root.val)
}

postorder(bt) // 4 5 2 6 7 3 1

二叉树的先中后序遍历（非递归实现）

先序遍历

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)
    }
}

preorder(bt) // 1 2 4 5 3 6 7

中序遍历

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
    }
}

inorder(bt) // 4 2 5 1 6 3 7

后序遍历

• 复用先序遍历
• 访问操作改成入栈操作
• 通过栈的特点输出实现逆序

const postorder = root => {
    if (!root) return
    const outputStack = []
    const stack = [root]

    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)
    }
}

postorder(bt) // 4 5 2 6 7 3 1

二叉树的最大深度

leeCode第104题

• 求最大深度，考虑使用深度优先遍历
• 在深度优先遍历过程中，记录每个节点所在的层级，找出最大的层级即可

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * 通过一个层次遍历的数组生成一棵二叉树
 * @param {any[]} array
 * @return {TreeNode}
 */
function getTreeFromLayerOrderArray(array) {
    let n = array.length;
    if (!n) return null;
    let index = 0;
    let root = new TreeNode(array[index++]);
    let queue = [root];
    while(index < n) {
        let top = queue.shift();
        let v = array[index++];
        top.left = v == null ? null : new TreeNode(v);
        if (index < n) {
            let v = array[index++];
            top.right = v == null ? null : new TreeNode(v);
        }
        if (top.left) queue.push(top.left);
        if (top.right) queue.push(top.right);
    }
    return root;
}

/**
  * 访问根节点
  * 对根节点的children挨个进行深度优先遍历
  * 
  * @param {TreeNode} root
  * @return {number}
  */
 const maxDepth = function(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
}

const btTree = getTreeFromLayerOrderArray([3, 9, 20, null, null, 15, 7])
console.log(maxDepth(btTree))

二叉树的最小深度

leeCode第111题

• 求最小深度，考虑使用广度优先遍历
• 在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级

/**
 * 新建一个队列，把根节点入队
 * 把队头出队并访问
 * 把对头的children挨个入队
 * 重复第二、三步，直到队列为空
 *
 * @param {TreeNode} root
  * @return {number}
 */
 const minDepth = function(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])
    }
}

const btTree = getTreeFromLayerOrderArray([3, 9, 20, null, null, 15, 7])
console.log(minDepth(btTree))

二叉树的层序遍历

leeCode第102题

• 层次遍历顺序就是广度优先遍历
• 在遍历时需要记录当前节点所处的层级，方便将其添加到不同的数组中

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
// 方法一
 const levelOrder = function(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
}

// 方法二
const levelOrder = function(root) {
    if (!root) return []
    const q = [root, 0]
    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 btTree = getTreeFromLayerOrderArray([3, 9, 20, null, null, 15, 7])
console.log(levelOrder(btTree))

二叉树的中序遍历

leeCode第94题

• 完全就是上面的中序遍历解法

/**
 * @param {TreeNode} root
 * @return {number[]}
 * @descript 递归版
 */
const inorderTraversal = function(root) {
    const res = []
    const rec = n => {
        if (!n) return
        rec(n.left)
        res.push(n.val)
        rec(n.right)
    }
    rec(root)
    return res
}

/**
 * @param {TreeNode} root
 * @return {number[]}
 * @descript 迭代版
 */
const inorderTraversal = function(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
}

const btTree = getTreeFromLayerOrderArray([1, null, 2, 3])
console.log(inorderTraversal(btTree))

路径总和

leeCode第112题

• 在深度优先遍历的过程中，记录当前路径的节点值的和
• 在叶子节点处，判断当前路径的节点值的和是否等于目标值

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
 const hasPathSum = function(root, targetSum) {
    if (!root) return false
    let res = false
    const dfs = (n, s) => {
        if (!n.left && !n.right && s === targetSum) { // 叶子节点并且值等于目标值
            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
}

const btTree = getTreeFromLayerOrderArray([5,4,8,11,null,13,4,7,2,null,null,null,1])
console.log(hasPathSum(btTree, 22))

遍历json的所有节点值

• 深度优先遍历

const json = {
    a: { b: { c: 1 } },
    d: [1, 2]
}

const dfs = (n, path) => {
    console.log((!path.length ? 'root' : path.join('.')) + '的值是：' + JSON.stringify(n))
    Object.keys(n).forEach(k => {
        dfs(n[k], path.concat(k))
    })
}

dfs(json, [])

// root的值是：{"a":{"b":{"c":1}},"d":[1,2]}
// a的值是：{"b":{"c":1}}
// a.b的值是：{"c":1}
// a.b.c的值是：1
// d的值是：[1,2]
// d.0的值是：1
// d.1的值是：2