问题陈述
- 在此示例中，我们可以看到输入有 null，这意味着给定的父级有子级，并且其由 null 分隔。
- 后序遍历意味着我们首先覆盖左子节点，然后覆盖右子节点，但由于我们的树是 n 元树，这意味着我们将从左到右进行后序遍历。
- 所以后序将是左 -> 右子节点 + 父节点。
- 输入：[1,null,3,2,4,null,5,6]
- 应该输出：[ [5,6,3], [ 2] , [4] , 1]
result =
new ArrayList<>();
postorder(Node root) {
if(root==
null)
return result;
sol1(root);
result.add(root.val);
return result;
}
private
void sol1(Node root){
if(root.children==
null){
return;
}
for(Node node:root.children){
sol1(node);
result.add(node.val);
}
}
}
思路：
我们将首先遍历每个子节点，然后进行递归调用，直到到达该节点没有任何子节点的阶段。
一旦我们有了这种情况，我们就可以返回我们的调用并将该节点添加到我们的结果中。
private void sol1(Node root){
if(root.children==null){
return;
}
for(Node node:root.children){
sol1(node);
result.add(node.val);
}
}
一旦我们完成了所有子节点的遍历，现在我们终于可以将根节点添加到列表中了。
sol1(root);
result.add(root.val);
return result;
还可以使用基于堆栈的方法在遍历节点时将每个子节点添加到堆栈中。
result =
new ArrayList<>();
postorder(Node root) {
sol2(root);
return result;
}
private
void sol2(Node root){
if(root.children==
null){
return;
}
Stack
stack =
new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node curr = stack.pop();
result.add(curr.val);
for(Node node: curr.children){
stack.push(node);
}
}
Collections.reverse(result);
}
}
- 这里要记住的一件事是，对于堆栈，我们从左向右移动，因此右侧将首先弹出并添加到列表中，作为与我们想要的第一个对比。
- 我们希望首先处决左孩子。
- 因此我们需要在最后反转结果列表：Collections.reverse(result);
结论
https://www.jdon.com/70540.html
原文地址:https://blog.csdn.net/cfy_banq/article/details/134821486
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_47920.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
