数据结构与算法——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;
    }
}