LintCode第1526-N叉树的前序遍历
描述
给定一个 N 叉树，返回其节点值的前序遍历
样例
输入 : {1,3,2,4#2#3,5,6#4#5#6}
输出: [1,3,5,6,2,4]这棵树如下所示（左侧的）
思路:该题使用递归法或者迭代法
方法1:递归法
代码如下:
/**
* Definition for Undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) {
* label = x;
* neighbors = new ArrayList<UndirectedGraphNode>();
* }
* }
*/
public class Solution {
/**
* @param root: the tree
* @return: pre order of the tree
*/
List<Integer> returnIntegerList=new ArrayList<>();
Set<UndirectedGraphNode> visited = new HashSet<>();//防止回边 这个属于可选项 可以将N叉树扩展到无向图
public List<Integer> preorder(UndirectedGraphNode root) {
// write your code here
returnIntegerList.clear(); // 清空上次的结果
visited.clear();//清空访问的结果 对于多次调用preorder是必不可少的
preOrderDFS(root);
return returnIntegerList;
}
public void preOrderDFS(UndirectedGraphNode node)
{
if(node==null|| visited.contains(node))
{
return;
}
visited.add(node); // 标记为访问过
returnIntegerList.add(node.label);
for(UndirectedGraphNode neighborNode:node.neighbors)
{
preOrderDFS(neighborNode);
}
}
}
迭代法:
代码如下:
/**
* Definition for Undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) {
* label = x;
* neighbors = new ArrayList<UndirectedGraphNode>();
* }
* }
*/
public List<Integer> preorder(UndirectedGraphNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Set<UndirectedGraphNode> visited = new HashSet<>();
Deque<UndirectedGraphNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
UndirectedGraphNode node = stack.pop();
if (!visited.add(node))
{
continue; // 已访问过就跳过
}
res.add(node.label); // 前序：先访问自己
// 为保证和递归一样的“从左到右”顺序，这里反向入栈 由于栈有先进后出的特性 所以需要反转
List<UndirectedGraphNode> ns = node.neighbors;
for (int i = ns.size() - 1; i >= 0; i--) {
stack.push(ns.get(i));
}
}
return res;
}