LeetCode演算法題-N-ary Tree Postorder Traversal（Java實現）
這是悅樂書的第269 次更新，第283 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第136題（順位題號是590）。給定一個n-ary樹，返回其節點值的後序遍歷。例如，給定一個3-ary樹：
1 /|\ 324 / \ 56
其後序遍歷結果為：[5,6,3,2,4,1]。
注意：遞迴解決方案是微不足道的，你可以用迭代的方式做嗎？
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
和昨天的題目求n-ary樹的前序遍歷結果類似，今天的題目是求其後序遍歷結果，也就是先左子樹，再右子樹，最後根節點，依舊使用遞迴的方法，只不過是將輔助方法裡的一行程式碼移動到for迴圈後面去執行而已，其他的地方和昨天的程式碼沒什麼區別。
/*
// 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> postorder(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;
}
if (root.children != null) {
for (Node n : root.children) {
getValue(n, list);
}
}
list.add(root.val);
return list;
}
}
03 第二種解法
使用迭代的方式。從題目的例子中可以看出，根節點在最後，最下面一層的節點在最前面，都是從左往右的順序，那麼反過來看，[1,4,2,3,6,5]，根節點被擺在了第一位，第二層的節點4從右邊換到了左邊，在左邊的3換到了右邊，第三層的節點也是如此。那麼我們可以直接使用棧，從根節點開始入棧，然後根節點第一個出棧，接著是第二層的第一個節點3入棧，然後是2入棧，最後是4入棧，進入第二次迴圈，首先出棧的是4，然後是3，最後是3，並且同時也將第三層的節點入棧了。最後我們將拿到的結果反轉即可，藉助集合工具類來完成。
/*
// 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> postorder(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 (Node n : temp.children) {
stack.push(n);
}
}
}
Collections.reverse(list);
return list;
}
}
04 第三種解法
針對上面的第二種解法，我們也可以不必反轉list，二是使用LinkedList來存節點值，藉助其addFirst方法，始終把節點值存入第一位。
/*
// 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> postorder(Node root) {
if (root == null) {
return new LinkedList<Integer>();
}
LinkedList<Integer> list = new LinkedList<Integer>();
Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
Node temp = stack.pop();
list.addFirst(temp.val);
if (temp.children != null) {
for (Node n : temp.children) {
stack.push(n);
}
}
}
return list;
}
}
05 第四種解法
使用兩個棧。第一個棧正常的做入棧出棧操作，從根節點開始，第二個棧在迴圈內部只做入棧操作，使得根節點被壓到了棧底部，而最後一個出棧的節點被壓到了第二個棧的棧頂，此時再對第二個棧進行出棧操作，就實現了後序遍歷。
/*
// 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> postorder(Node root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> list = new ArrayList<Integer>();
Stack<Node> stack = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
Node temp = stack.pop();
stack2.push(temp);
if (temp.children != null) {
for (Node n : temp.children) {
stack.push(n);
}
}
}
while (!stack2.isEmpty()) {
list.add(stack2.pop().val);
}
return list;
}
}
06 小結
演算法專題目前已日更超過四個月 ，演算法題文章136 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！