注:个人算法比较菜,由于是第一遍刷题,代码质量可能都不好,这里暂时做个刷题记录:)。
题目:
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7],
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvle7s/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
图解:
1 / 2 3 / / 4 5 6 7
init two array: larr [1] rarr []
larr rarr visit node [1] [] [] [2, 3] 1 [6,7] [2] 3 [4,5,6,7] [] 2 [5,6,7] [] 4 ... [] ...
代码:
function TreeNode(val){ this.val = val; this.left = this.right = null; } /** *层次遍历构造二叉树 */ function createBinaryTree(arr){ var p = new TreeNode(arr[0]); var k = 0; var len = arr.length; var buildTree = function(node, i){ if(2*i+1<len && arr[2*i+1]!==null){ node.left = new TreeNode(arr[2*i+1]); node.left && buildTree(node.left, 2*i+1) } if(2*i+2<len && arr[2*i+2]!==null){ node.right = new TreeNode(arr[2*i+2]); node.right && buildTree(node.right, 2*i+2); } }; buildTree(p, 0); return p; } /** * @param {TreeNode} root * @return {number[][]} */ var zigzagLevelOrder = function(root) { if(!root) return []; var flag = true; var result = []; var larr = [root]; var rarr = []; var p = null; var tmp = []; while(larr.length>0||rarr.length>0){ if(flag){ tmp = []; while(larr.length>0){ p = larr.shift(); p && tmp.push(p.val); var tmp2 = []; p.left && tmp2.push(p.left); p.right && tmp2.push(p.right); rarr = rarr.concat(tmp2); } result.push(tmp); }else{ tmp = []; while(rarr.length>0){ p = rarr.pop(); p && tmp.push(p.val); var tmp2 = []; p.left && tmp2.push(p.left); p.right && tmp2.push(p.right); larr = tmp2.concat(larr); } result.push(tmp); } flag=!flag; } return result; }; var arr = [3,9,20,null,null,15,7]; var tree = createBinaryTree(arr); //console.log(tree); //var tree = new TreeNode(1); var result = zigzagLevelOrder(tree); console.log('result',result);