首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。