给定一颗 N 叉树
的根节点,返回后序遍历后的数组.
例 :
给予树:
1
/ | \
3 2 4
/ \
5 6
将其后序遍历返回: [5,6,3,2,4,1].
和二叉树的中序遍历差不多,需要注意处理好子节点的顺序即可。
非递归解法:
/*
// 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) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.peek();
List<Node> children = node.children;
if (children != null && children.size() != 0) {
for (int i = children.size() - 1; i >= 0; i--) {
stack.add(children.get(i));
}
} else {
list.add(stack.pop().val);
}
node.children = new ArrayList<>();
}
return 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 {
List<Integer> list = new ArrayList<>();
public List<Integer> postorder(Node root) {
if (root == null) {
return list;
}
for (Node child : root.children) {
postorder(child);
}
list.add(root.val);
return list;
}
}
Runtime: 1 ms, faster than 100.00% of Java online submissions for N-ary Tree Postorder Traversal. Memory Usage: 48.2 MB, less than 40.66% of Java online submissions for N-ary Tree Postorder Traversal.