iT邦幫忙

2022 iThome 鐵人賽

DAY 21
0

題目說明:給一棵n-ary樹的root,要你用preorder traversal(前序遍歷)的方式求出這棵樹的數值

Case 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]

Case 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

解題思路:其實和二元樹的preorder概念是類似的(關於preorder的走法可以參考我的這篇文章),只是二元樹有分成左子樹和右子樹,但在這邊只有root它的子樹(children)。如果用虛擬碼表示的話可以寫成以下的方式

list={}
preorder(root){
    if (root==null){
        return list;//root為null空值時直接回傳list
    }
    else{
        list.add(root.val);//list加上root的數值
        for(node in root.children){
            preorder(node);//對應root的子樹進行preorder
        }
    } 
    return list;
}

附上程式碼
Java

class Solution {
    List<Integer> l=new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if(root==null){return l;}
        else{
            l.add(root.val);
            for(Node c:root.children){
                preorder(c);
            }
        }
        return l;
    }
}

上一篇
Day 20 N-th Tribonacci Number
下一篇
Day 22 Triangle
系列文
從leetcode學習資料結構和演算法31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言