題目說明:給一棵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;
}
}