多叉树的递归/层序遍历

labuladong原创约 1248 字

前置知识

阅读本文前，你需要先学习：

一句话总结

多叉树结构就是二叉树结构的延伸，二叉树是特殊的多叉树。森林是指多个多叉树的集合。

多叉树的遍历就是二叉树遍历的延伸。

二叉树的节点长这样，每个节点有两个子节点：

java 🟢

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

cpp 🤖

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

python 🤖

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

go 🤖

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

javascript 🤖

var TreeNode = function(val) {
    this.val = val;
    this.left = null;
    this.right = null;
};

多叉树的节点长这样，每个节点有任意个子节点：

java 🟢

class Node {
    int val;
    List<Node> children;
}

cpp 🤖

class Node {
public:
    int val;
    vector<Node*> children;
};

python 🤖

class Node:
    def __init__(self, val: int):
        self.val = val
        self.children = []

go 🤖

type Node struct {
    val      int
    children []*Node
}

javascript 🤖

var Node = function(val) {
    this.val = val;
    this.children = [];
}

就这点区别，其他没了。

森林

这里介绍一下「森林」这个名词，后面讲到 Union Find 并查集算法时，会用到这个概念。

很简单，森林就是多个多叉树的集合。一棵多叉树其实也是一个特殊的森林。

在并查集算法中，我们会同时持有多棵多叉树的根节点，那么这些根节点的集合就是一个森林。

接下来说下多叉树的遍历，和二叉树一样，也就递归遍历（DFS）和层序遍历（BFS）两种。

对比二叉树的遍历框架看多叉树的遍历框架吧：