二叉树深度&广度遍历

二叉树的数据结构在js中可以如此表示:

const tree = {
    value: 1,
    left: {
        value: 2,
        left: {
            value: 4,
            left: {
                value: 8
            },
            right: {
                value: 9
            }
        },
        right: {
            value: 5
        }
    },
    right: {
        value: 3,
        left: {
            value: 6
        },
        right: {
            value: 7
        }
    }
}

我们分别采用深度和广度遍历一遍：

深度优先

此处就使用前序遍历了

递归实现

function dfsRecursion(tree) {
    let res = [];
    function dfs(node){
        if(node) {
            res.push(node.value);
            dfs(node.left);
            dfs(node.right);
        }
    }
    dfs(tree);
    return res;
}

非递归实现

/**
 * @param tree 
 * 非递归实现，需要自行实现“回溯”，可以使用栈来巧妙实现
 * 将某个节点的右节点、左节点依次压倒栈中，会先消费该左节点，再次将其右子节点、左子节点压入栈...
 */
function dfsNonRecursion(tree) {
    let arr = [];
    let res = [];
    arr.push(tree);
    while (arr.length) {
        const node = arr.pop();
        res.push(node.value);
        if (node.right) {
            arr.push(node.right);
        }
        if (node.left) {
            arr.push(node.left);
        }
    }
    return res
}

广度优先

function bfs(tree) {
    let res = [];
    let arr = [];
    arr.push(tree);
    while(arr.length) {
        const node = arr.shift();
        res.push(node.value);
        if(node.left) {
            arr.push(node.left);
        }
        if(node.right) {
            arr.push(node.right);
        }
    }
    return res;
}