官網題目敘述:

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

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

    3
   / \
  9  20
    /  \
   15   7

 

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

 

先附上通關證明(感覺應該有更好的方法,歡迎分享給我..)

我的想法就是先找出Top to bottom 每一層所有的節點,一層一層的找下去,直到沒有下一層為止,然後把結果串起來。(十分無腦的做法?

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

var levelOrder = function(root) {

    // 檢查輸入是否為空

    if(root==null) return [];

    var start = [];

    var startArray = [];

    // 把Root放進Array然後開始跑我們的遞迴。

    // startArray算是初始化最後result。

    start.push(root);

    return letgo(start,startArray);

};
var letgo = function(nodeArray , result){

    var thislevel = [];

    var nextNodeArray = [];

    // 輪詢每一層所有的節點並且將值塞入thislevel的陣列。

    // 順便準備好下一層要輪詢的節點。

    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);

    }

    result.push(thislevel);

    // 如果沒有下一層的節點就回傳結果,還有就繼續做遞回。

    if(nextNodeArray.length<1)return result;

    return letgo(nextNodeArray,result);

}

 

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

    西瓜是肥貓

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