多叉树的递归/层序遍历

labuladong原创约 1166 字

前置知识

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

二叉树的递归/层序遍历

一句话总结

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

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

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

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）两种。

递归遍历（DFS）

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

java 🟢

// 二叉树的遍历框架
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

// N 叉树的遍历框架
void traverse(Node root) {
    if (root == null) {
        return;
    }
    // 前序位置
    for (Node child : root.children) {
        traverse(child);
    }
    // 后序位置
}

cpp 🤖

// 二叉树的遍历框架
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

// N 叉树的遍历框架
void traverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    for (Node* child : root->children) {
        traverse(child);
    }
    // 后序位置
}

python 🤖

# 二叉树的遍历框架
def traverse_binary_tree(root):
    if root is None:
        return
    # 前序位置
    traverse_binary_tree(root.left)
    # 中序位置
    traverse_binary_tree(root.right)
    # 后序位置


# N 叉树的遍历框架
def traverse_n_ary_tree(root):
    if root is None:
        return
    # 前序位置
    for child in root.children:
        traverse_n_ary_tree(child)
    # 后序位置

go 🤖

// 二叉树的遍历框架
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // 前序位置
    traverse(root.Left)
    // 中序位置
    traverse(root.Right)
    // 后序位置
}

// N 叉树的遍历框架
func traverseNary(root *Node) {
    if root == nil {
        return
    }
    // 前序位置
    for _, child := range root.Children {
        traverseNary(child)
    }
    // 后序位置
}

javascript 🤖

// 二叉树的遍历框架
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
};

// N 叉树的遍历框架
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // 前序位置
    for (var i = 0; i < root.children.length; i++) {
        traverse(root.children[i]);
    }
    // 后序位置
};

唯一的区别是，多叉树没有了中序位置，因为可能有多个节点嘛，所谓的中序位置也就没什么意义了。

可以看看下面这个可视化面板，点击其中 preorderResult.push 或 postorderResult.push 的代码部分，观察前序和后序遍历的执行顺序，其实和二叉树是一样的：

层序遍历（BFS）

多叉树的层序遍历和二叉树的层序遍历一样，都是用队列来实现，无非就是把二叉树的左右子节点换成了多叉树的所有子节点。所以多叉树的层序遍历也有三种写法，下面一一列举。

写法一

第一种层序遍历写法：

java 🟢

void levelOrderTraverse(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        Node cur = q.poll();
        // 访问 cur 节点
        System.out.println(cur.val);

        // 把 cur 的所有子节点加入队列
        for (Node child : cur.children) {
            q.offer(child);
        }
    }
}

cpp 🤖

void levelOrderTraverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        // 访问 cur 节点
        std::cout << cur->val << std::endl;

        // 把 cur 的所有子节点加入队列
        for (Node* child : cur->children) {
            q.push(child);
        }
    }
}

python 🤖

from collections import deque

def level_order_traverse(root):
    if root is None:
        return
    
    q = deque()
    q.append(root)
    
    while q:
        cur = q.popleft()
        # 访问 cur 节点
        print(cur.val)
        
        # 把 cur 的所有子节点加入队列
        for child in cur.children:
            q.append(child)

go 🤖

func levelOrderTraverse(root *Node) {
	if root == nil {
		return
	}
	q := []*Node{}
	q = append(q, root)
	for len(q) > 0 {
		cur := q[0]
		q = q[1:]
		// 访问 cur 节点
		fmt.Println(cur.Val)

		// 把 cur 的所有子节点加入队列
		for _, child := range cur.Children {
			q = append(q, child)
		}
	}
}

javascript 🤖

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    q.push(root);
    while (q.length !== 0) {
        var cur = q.shift();
        // 访问 cur 节点
        console.log(cur.val);

        // 把 cur 的所有子节点加入队列
        for (var child of cur.children) {
            q.push(child);
        }
    }
}

写法二

第二种能够记录节点深度的层序遍历写法：

java 🟢

void levelOrderTraverse(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> q = new LinkedList<>();
    q.offer(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    int depth = 1;

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            // 访问 cur 节点，同时知道它所在的层数
            System.out.println("depth = " + depth + ", val = " + cur.val);

            for (Node child : cur.children) {
                q.offer(child);
            }
        }
        depth++;
    }
}

cpp 🤖

#include <iostream>
#include <queue>
#include <vector>

void levelOrderTraverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<Node*> q;
    q.push(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    int depth = 1;

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            Node* cur = q.front();
            q.pop();
            // 访问 cur 节点，同时知道它所在的层数
            std::cout << "depth = " << depth << ", val = " << cur->val << std::endl;

            for (Node* child : cur->children) {
                q.push(child);
            }
        }
        depth++;
    }
}

python 🤖

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    # 记录当前遍历到的层数（根节点视为第 1 层）
    depth = 1

    while q:
        sz = len(q)
        for i in range(sz):
            cur = q.popleft()
            # 访问 cur 节点，同时知道它所在的层数
            print(f"depth = {depth}, val = {cur.val}")

            for child in cur.children:
                q.append(child)
        depth += 1

go 🤖

func levelOrderTraverse(root *Node) {
    if root == nil {
        return
    }
    q := []*Node{root}
    // 记录当前遍历到的层数（根节点视为第 1 层）
    depth := 1

    for len(q) > 0 {
        sz := len(q)
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            // 访问 cur 节点，同时知道它所在的层数
            fmt.Printf("depth = %d, val = %d\n", depth, cur.val)

            for _, child := range cur.children {
                q = append(q, child)
            }
        }
        depth++
    }
}

javascript 🤖

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    q.push(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    var depth = 1;

    while (q.length !== 0) {
        var sz = q.length;
        for (var i = 0; i < sz; i++) {
            var cur = q.shift();
            // 访问 cur 节点，同时知道它所在的层数
            console.log("depth = " + depth + ", val = " + cur.val);

            for (var j = 0; j < cur.children.length; j++) {
                q.push(cur.children[j]);
            }
        }
        depth++;
    }
}

写法三

第三种能够适配不同权重边的写法：

java 🟢

class State {
    Node node;
    int depth;

    public State(Node node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

void levelOrderTraverse(Node root) {
    if (root == null) {
        return;
    }
    Queue<State> q = new LinkedList<>();
    // 记录当前遍历到的层数（根节点视为第 1 层）
    q.offer(new State(root, 1));

    while (!q.isEmpty()) {
        State state = q.poll();
        Node cur = state.node;
        int depth = state.depth;
        // 访问 cur 节点，同时知道它所在的层数
        System.out.println("depth = " + depth + ", val = " + cur.val);

        for (Node child : cur.children) {
            q.offer(new State(child, depth + 1));
        }
    }
}

cpp 🤖

class State {
public:
    Node* node;
    int depth;

    State(Node* node, int depth) : node(node), depth(depth) {}
};

void levelOrderTraverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<State> q;
    // 记录当前遍历到的层数（根节点视为第 1 层）
    q.push(State(root, 1));

    while (!q.empty()) {
        State state = q.front();
        q.pop();
        Node* cur = state.node;
        int depth = state.depth;
        // 访问 cur 节点，同时知道它所在的层数
        std::cout << "depth = " << depth << ", val = " << cur->val << std::endl;

        for (Node* child : cur->children) {
            q.push(State(child, depth + 1));
        }
    }
}

python 🤖

class State:
    def __init__(self, node, depth):
        self.node = node
        self.depth = depth

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    # 记录当前遍历到的层数（根节点视为第 1 层）
    q.append(State(root, 1))

    while q:
        state = q.popleft()
        cur = state.node
        depth = state.depth
        # 访问 cur 节点，同时知道它所在的层数
        print(f"depth = {depth}, val = {cur.val}")

        for child in cur.children:
            q.append(State(child, depth + 1))

go 🤖

type State struct {
    node  *Node
    depth int
}

func levelOrderTraverse(root *Node) {
    if root == nil {
        return
    }
    q := []State{}
    // 记录当前遍历到的层数（根节点视为第 1 层）
    q = append(q, State{root, 1})

    for len(q) > 0 {
        state := q[0]
        q = q[1:]
        cur := state.node
        depth := state.depth
        // 访问 cur 节点，同时知道它所在的层数
        fmt.Printf("depth = %d, val = %d\n", depth, cur.Val)

        for _, child := range cur.Children {
            q = append(q, State{child, depth + 1})
        }
    }
}

javascript 🤖

function State(node, depth) {
    this.node = node;
    this.depth = depth;
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    // 记录当前遍历到的层数（根节点视为第 1 层）
    q.push(new State(root, 1));

    while (q.length !== 0) {
        var state = q.shift();
        var cur = state.node;
        var depth = state.depth;
        // 访问 cur 节点，同时知道它所在的层数
        console.log("depth = " + depth + ", val = " + cur.val);

        for (var i = 0; i < cur.children.length; i++) {
            q.push(new State(cur.children[i], depth + 1));
        }
    }
}

没啥好说的，有不明白的区对照前文二叉树遍历的层序遍历代码和可视化面板吧。