官網題目敘述:

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

 

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]
先附上通關證明(感覺應該有更好的方法,歡迎分享給我..)

 

 

解法:這個跟102應該算是家族題,其實就把102的解法加上一次要倒序一次不用倒序的boolean值跟倒序方法就可以了。

然後把這個想法練習寫成 Js :

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if(root==null) return [];
    var start = [];
    var startArray = [];
    start.push(root);
    return letgo(start,startArray,true);
};

var letgo = function(nodeArray , result , toright){
    var thislevel = [];
    var nextNodeArray = [];
    for (var i = 0; i < nodeArray.length; i++) {
        thislevel.push(nodeArray[i].val);
        if(nodeArray[i].left!=null)nextNodeArray.push(nodeArray[i].left);
        if(nodeArray[i].right!=null)nextNodeArray.push(nodeArray[i].right);
    }
    if(!toright){
        thislevel = revese(thislevel);
    }
    result.push(thislevel);
    if(nextNodeArray.length<1)return result;
    return letgo(nextNodeArray,result,!toright);
}

var revese = function(array){
    for (var y = 0 ; y < (array.length-1 ) -y; y++) {
        z = (array.length-1) -y;
        temp = array[y] ;
        array[y] = array[z];
        array[z] = temp;
    }
    return array;
}

 

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 Deyu 的頭像
    Deyu

    西瓜是肥貓

    Deyu 發表在 痞客邦 留言(0) 人氣()