首页 > 代码库 > Binary Tree Level Order Traversal II

Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/#/solutions

这题跟层序遍历没有什么不同,只是把最后结果reverse 一下而已。不知道还有没有其他的套路?

可以分别用BFS 和DFS,后者要更简洁一点。

BFS:

/** * @param {TreeNode} root * @return {number[][]} */var levelOrderBottom = function(root) {    var queue = [[root]];    var ret = [];    while (queue.length !== 0) {        var top = queue.shift();        var tr = [];        var tq = [];        for (var i = 0; i < top.length; i++) {            if (top[i]) {                tr.push(top[i].val);                tq.push(top[i].left, top[i].right);            }        }        if (tq.length > 0) queue.push(tq);        if (tr.length > 0) ret.push(tr);    }    return ret.reverse();};

DFS:

var levelOrderBottom = function(root) {    var ret = [];    function iter(node, level, ret) {        if (!node) return;        ret[level] = ret[level] || [];        ret[level].push(node.val);        iter(node.left, level+1, ret);        iter(node.right, level+1, ret);    }    iter(root, 0, ret);    return ret.reverse();}

 

写这题没花什么时间,但是写构造二叉树的代码和测试倒是挠头了一下T_T

通过层序数组构造二叉树,中序遍历和层序遍历

function TreeNode(val) {    this.val = val;    this.left = this.right = null;}function makeTree(arr) {    function makeIter(i, limit) {        if (!arr[i]) return null;        if (i >= limit) return null;        var node = new TreeNode(arr[i]);        node.left = makeIter(2*i+1, limit);        node.right = makeIter(2*i+2, limit);        return node;    }    return makeIter(0, arr.length);}function middleOrderTraversal(node) {    function iter(node, ret) {        if (!node) {ret.push(null); return;}        ret.push(node.val);        iter(node.left, ret);        iter(node.right, ret);    }    var ret = [];    iter(node, ret);    console.log(ret);}function levelOrderTraversal(node) {    var queue = [node];    var ret = [];    while (queue.length !== 0) {        var top = queue.shift();        if (top !== null) {            ret.push(top.val);            queue.push(top.left, top.right);        } else {            ret.push(null);        }    }    console.log(ret);}

 

Binary Tree Level Order Traversal II