【Golang主题学习月】 刷题比玩游戏好多了，成就感越来越强，每天坚持刷一道题，每天锻炼30分钟，等8块腹肌,等大厂offer.
😄
我相信，如果在面试中遇到此题，逻辑清晰、正确表达出来、手撕
应该会超过一部分的面试者。
对树不熟悉的朋友，可以看看前面的基础训练题哦！
leecode 589. N 叉树的前序遍历
给定一个 N 叉树，返回其节点值的 前序遍历 。
N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
进阶：
递归法很简单，你可以使用迭代法完成此题吗?
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]
示例 2：
输入：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]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
提示：
N 叉树的高度小于或等于 1000
节点总数在范围 [0, 10^4] 内
参考代码
每组子节点由空值 null 分隔
首先的明白题的意思，每组子节点代表，有根，有左节点或者右节点，现在去看示例 2应该就没有问题了吧
GO语言版 dfs
之前说二叉树的前序遍历时用的栈，同样，在这里也用栈，思路也完全一样。
栈是先进后出。
前序遍历时根、左、右
很明显，先把根怼进栈，有左节点就入栈，直接没有左节点。
因为先进后出，最后加入的节点先出来。
右边也是同理。
// 定义一个n叉树，一根多子
class Node {
int val;
List<Node> children;
Node(int x, List<Node> children) {
val = x;
children = children;
}
}
复制代码var res []int
func preorder(root *Node) []int {
res = []int{}
dfs(root)
return res
}
func dfs(root *Node) {
if root != nil {
res = append(res, root.Val)
for _,n := range root.Children {
dfs(n)
}
}
}
复制代码迭代版
func preorder(root *Node) []int {
var res []int
var stack = []*Node{root}
for 0 < len(stack) {
for root != nil {
res = append(res, root.Val) //前序输出
if 0 == len(root.Children) {
break
}
for i := len(root.Children) - 1; 0 < i; i-- {
stack = append(stack, root.Children[i]) //入栈
}
root = root.Children[0]
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
return res
}
复制代码JAVA
// 迭代
class Solution {
public List<Integer> preorder(Node root){
List<Integer> list = new ArrayList<>();
Deque<Node> stack = new LinkedList<>();
stack.push(root);
if(root == null) return list;
while(!stack.isEmpty()){
//当前栈顶节点出栈
Node node = stack.pop();
//将值加入列表
list.add(node.val);
int size = node.children.size();
//将当前节点的孩子们从右到左入栈
for(int i = size - 1; i >= 0; i--){
stack.push(node.children.get(i));
}
}
return list;
}
}
// 递归
class Solution {
public List<Integer> preorder(Node root){
List<Integer> list = new ArrayList<>();
helper(root, list);
return list;
}
public void helper(Node root, List<Integer> list){
if(root == null) return;
list.add(root.val);
for(Node child: root.children){
helper(child, list);
}
}
}
复制代码真心感谢帅逼靓女们能看到这里，如果这个文章写得还不错，觉得有点东西的话
求点赞👍 求关注❤️ 求分享👥 对8块腹肌的我来说真的 非常有用！！！
如果本篇博客有任何错误，请批评指教，不胜感激 ！❤️❤️❤️❤️
近期评论