LeetCode演算法題-N-ary Tree Preorder Traversal（Java實現）
摘要：
這是悅樂書的第268
次更新，第282
篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第135題（順位題號是589）。給定一個n-ary樹，返回其節點值的前序遍歷。例如，給定一個3-ary樹：
1
...
這是悅樂書的第268 次更新，第282 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第135題（順位題號是589）。給定一個n-ary樹，返回其節點值的前序遍歷。例如，給定一個3-ary樹：
1 /|\ 324 / \ 56
其前序遍歷結果為：[1,3,5,6,2,4]。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
利用遞迴。二叉樹前序遍歷是從根節點開始，然後是左子樹，最後是右子樹，題目給的是N-ary樹，但是遍歷節點的順序還是和二叉樹一樣，從根節點開始，然後對其子節點（list陣列）進行遍歷，其子節點進行前序遍歷，和題目性質一樣，可以直接使用遞迴的方式參與計算。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> list = new ArrayList<Integer>();
getValue(root, list);
return list;
}
public List<Integer> getValue(Node root, List<Integer> list) {
if (root == null) {
return null;
}
list.add(root.val);
if (root.children != null) {
for (Node n : root.children) {
getValue(n, list);
}
}
return list;
}
}
03 第二種解法
我們也可以使用迭代的方式來實現前序遍歷。這裡我們使用棧，藉助其先進後出的特性，有一點需要注意的是，在處理其子節點時，我們需要從後往前入棧，這樣出棧的時候就是從前往後了。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> list = new ArrayList<Integer>();
Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
Node temp = stack.pop();
list.add(temp.val);
if (temp.children != null) {
for (int i=temp.children.size()-1; i >= 0; i--) {
stack.push(temp.children.get(i));
}
}
}
return list;
}
}
04 小結
演算法專題目前已日更超過四個月 ，演算法題文章135 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！