【数据结构与算法】102. 二叉树的层序遍历

[sayid760]

原题

[sayid760]

// 模拟树结构
// 节点对象
class Node {
    constructor(data) {
        this.root = this;
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// 二叉树
class BST {
    constructor() {
        this.root = null;
    }

    // 插入节点
    insert(data) {
        if (!data) return
        let newNode = new Node(data);
        let insertNode = (node, newNode) => {
            if (newNode.data < node.data) {
                if (node.left === null) {
                    node.left = newNode;
                } else {
                    insertNode(node.left, newNode);
                }
            } else {
                if (node.right === null) {
                    node.right = newNode;
                } else {
                    insertNode(node.right, newNode)
                }
            }
        };

        if (!this.root) {
            this.root = newNode;
        } else {
            insertNode(this.root, newNode)
        }
    }
}

let datas = [3, 2, 15, null, null, 7, 20]
let bst = new BST();
datas.forEach(data => {
    bst.insert(data)
})

方法一：深度优先搜索

var levelOrder = function (root) {
    if (!root) return []
    let res = []
    dfs(root, 0, res)
    return res
};

function dfs(root, level, res) {
    if (root) {
        if (!res[level]) res[level] = []
        res[level].push(root.data)
        dfs(root.left, level + 1, res)
        dfs(root.right, level + 1, res)
    }
}

// 方法二： 广度优先搜索

var levelOrder = function (root) {
    if(!root) return []
    console.log([root])
    let queue = [root]  // [Node {root: Node, data: 3, left: Node, right: Node}]
    let res = []
    while(queue.length>0){
        let len = queue.length
        let arr = []
        while(len){
            let node = queue.shift()
            arr.push(node.data)
            if(node.left) queue.push(node.left)
            if(node.right) queue.push(node.right)
            console.log(queue)
            len--
        }
        res.push(arr)
    }
    return res
}
console.log(levelOrder(bst.root))
/* 输出
[
  [3],
  [2,15],
  [7,20]
]
*/