数据结构与算法——N叉树（自学笔记）

本文参考 N 叉树 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

遍历

• 前序遍历：A->B->C->E->F->D->G
• 后序遍历：B->E->F->C->G->D->A
• 层序遍历：A->B->C->D->E->F->G

(中序遍历只在二叉树有明确定义)

前序遍历

递归

与二叉树一样

import java.util.*;// 定义N叉树节点
class Node{public int val;public List<Node> children; // 使用链表定义子节点public Node(){}public Node(int val){this.val = val;}public Node(int val, List<Node> children){this.val = val;this.children = children;}
}class Solution {public List<Integer> preorder(Node root){List<Integer> res = new ArrayList<Integer>();preorderRecursion(root,res);return res;}public void preorderRecursion(Node root, List<Integer> res){if(root == null){return;}res.add(root.val);for(Node node : root.children){preorderRecursion(node, res);}}
}

• 时间复杂度：O(N)，其中 N 是树的节点数。
• 空间复杂度：O(N)，即树的高度，最坏情况下递归栈和结果存储的空间需要O(N)的空间。

迭代

与二叉树不一样，很巧妙

class Solution {public List<Integer> preorder(Node root){List<Integer> res = new ArrayList<Integer>();if(root == null){return res;}Deque<Node> stack = new LinkedList<Node>();stack.push(root);while(!stack.isEmpty()){Node node = stack.pop();res.add(node.val);// 逆序入栈for(int i = node.children.size() - 1; i >= 0 ; i--){ stack.push(node.children.get(i)); }}return res;}
}

• 时间复杂度：O(N)，其中 N 是树的节点数。
• 空间复杂度：O(N)，即树的高度，最坏情况下递归栈和结果存储的空间需要O(N)的空间。

后序遍历

递归

class Solution {public List<Integer> postorder(Node root){List<Integer> res = new ArrayList<Integer>();postorderRecursion(root,res);return res;}public void postorderRecursion(Node root, List<Integer> res){if(root == null){return;}for(Node node : root.children){postorderRecursion(node, res);}res.add(root.val); // 与前序遍历的唯一区别}
}

迭代

与前序遍历相似

class Solution {public List<Integer> postorder(Node root) {// 创建一个列表用来存储后序遍历的结果List<Integer> res = new ArrayList<>();// 如果树为空，直接返回空结果if (root == null) {return res;}// 使用栈进行遍历，栈用来模拟递归Deque<Node> stack = new ArrayDeque<Node>();// 创建一个集合，用来记录已经访问过的节点Set<Node> visited = new HashSet<Node>();// 将根节点推入栈中stack.push(root);// 遍历栈中的节点，直到栈为空while (!stack.isEmpty()) {// 获取栈顶的节点Node node = stack.peek();// 如果当前节点没有子节点（叶子节点），或者子节点已经遍历过if (node.children.size() == 0 || visited.contains(node)) {// 弹出栈顶元素，并将其值加入结果列表stack.pop();res.add(node.val);// 继续下一次循环continue;}// 如果当前节点有未访问的子节点，逆序将子节点压入栈中for (int i = node.children.size() - 1; i >= 0; --i) {stack.push(node.children.get(i));}// 将当前节点标记为已访问visited.add(node);}// 返回存储后序遍历结果的列表return res;}}

• 时间复杂度：O(N)，其中 N 是树的节点数。
• 空间复杂度：O(N)，即树的高度，最坏情况下递归栈和结果存储的空间需要O(N)的空间。

层序遍历

常规方法

class Solution {public List<List<Integer>> levelOrder (Node root){List<List<Integer>> res = new ArrayList<>();if(root == null){return res;}Queue<Node> queue = new LinkedList<>();Node node = root;queue.offer(node);while(!queue.isEmpty()){List<Integer> level = new ArrayList<>(); // 创建子链表int size = queue.size(); // 计算当前层的大小for(int i = 0; i < size; i++){node = queue.poll(); // 把当前层的节点依次弹出，并加入小链表level.add(node.val);for(Node p : node.children){queue.offer(p); // 把下一层的节点依次加入队列}}res.add(level); // 将小链表加入大链表}return res;}
}

• 时间复杂度：O(N)，其中 N 是树的节点数。
• 空间复杂度：O(N)，即树的高度，最坏情况下递归栈和结果存储的空间需要O(N)的空间。

递归

N叉树的最大深度

class Solution {public int maxDepth(Node root){if(root == null){return 0;}int maxNmu = 0;List<Node> children = root.children;if (children != null){ // 增强for可以自动处理空集合，但不能处理null，最好添加判断for(Node p : children){maxNmu = Math.max(maxNmu,maxDepth(p)); // 找出最深层}}return maxNmu + 1;}
}

时间复杂度：O(n)，其中 n 为 N 叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：O(height)，其中 height 表示 N 叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于 N 叉树的高度。