BFS

:::success

• Shortest Cycle Containing Target Node :::

练习：

剑指 Offer 32 - I. 从上到下打印二叉树

var levelOrder = function(root) {
    if (root == null) return [];
    let res = [];
    let tmp = [root];
    while (tmp.length > 0) {
        let node = tmp.shift()
        res.push(node.val);
        node.left != null && tmp.push(node.left)
        node.right != null && tmp.push(node.right)
    }
    return res;
};

剑指 Offer 32 - II. 从上到下打印二叉树 II

var levelOrder = function(root) {
    if (root == null) return [];
    let res = [];
    let queue = [root]
    while (queue.length > 0) {
        let curRes = []
        let nextQueue = [];
        for (let node of queue) {
            curRes.push(node.val)
            node.left != null && nextQueue.push(node.left)
            node.right != null && nextQueue.push(node.right)
        }
        res.push(curRes);
        queue = nextQueue
    }
    return res;
};

方法2: dfs

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

function dfs (root, depth, res) {
    if (root == null) return;
    if (!res[depth]) {
        res[depth] = [];
    }
    res[depth].push(root.val)
    root.left != null && dfs(root.left, depth+1, res)
    root.right != null && dfs(root.right, depth+1, res)
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

同⬆️， 忽略

var levelOrder = function(root) {
    if (root == null) return [];
    let res = [];
    let queue = [root];
    while (queue.length > 0) {
        let curRes = [];
        let nextQueue = [];
        for (let node of queue) {
            curRes.push(node.val)
            node.left != null && nextQueue.push(node.left)
            node.right != null && nextQueue.push(node.right)
        }
        if (res.length % 2 == 1) {
            curRes.reverse()
        }
        res.push(curRes)
        queue = nextQueue
    }
    return res;
};

dfs方法实现

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

function dfs(root, depth, res) {
    if (root == null) retur;
    if (!res[depth]) {
        res[depth] = []
    }
    if (depth % 2 == 0) {
        res[depth].push(root.val)
    } else {
        res[depth].unshift(root.val)
    }
    depth++;
    root.left != null && dfs(root.left, depth, res);
    root.right != null && dfs(root.right, depth, res);
 }

剑指 Offer 37. 序列化二叉树

var serialize = function(root) {
    if (root == null) return '[]'; 
    // bfs
    let res = []
    let queue = [root];
    while (queue.length > 0) {
        let node = queue.shift();
        res.push(node == null ? 'null' : node.val)
        if (node != null) {
            queue.push(node.left);
            queue.push(node.right);
        }
    }
    // console.log(res.join(','))
    return `[${res.join(',')}]`
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    if (data == '[]') return null;
    let arr = data.slice(1, -1).split(',')
    let root = new TreeNode(arr[0])
    let queue = [root];
    for (let i = 1; i < arr.length; i += 2) {
        const node = queue.shift();
        if (arr[i] != 'null') {
            let left = new TreeNode(arr[i])
            node.left = left
            queue.push(left)
        }
        if (arr[i+1] != 'null') {
            let right = new TreeNode(arr[i+1])
            node.right = right
            queue.push(right)
        }
    }
    return root;
};