將 N 叉樹編碼為二元樹

作者：Grey

原文地址：

題目描述

將一棵n叉樹編碼為一棵二元樹，並對二元樹進行解碼，得到原始的n叉樹。 n叉樹是一棵有根樹，其中每個節點的子樹不超過n個。類似地，二元樹是一棵有根樹，其中每個節點的子樹不超過2個。編碼/解碼演演算法的工作方式不受限制。您只需要確保一個n叉樹可以被編碼為一個二元樹，並且這個二元樹可以被解碼為原始的n叉樹結構。

題目連結：LintCode 1530 · Encode N-ary Tree to Binary Tree

一棵 N 叉樹的範例如下

二元樹的資料結構如下

class TreeNode {
    public int val;
    public TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

N 叉樹的資料結構如下

class UndirectedGraphNode {
     int label;
     List<UndirectedGraphNode> neighbors;
     UndirectedGraphNode(int x) {
         label = x;
         neighbors = new ArrayList<UndirectedGraphNode>();
     }
}

每個節點有屬於自己的 label 值，也有若干個孩子節點，即List<UndirectedGraphNode> neighbors。

我們需要實現如下兩個方法

// N 叉樹編碼成 二元樹
TreeNode encode(UndirectedGraphNode root)
// 二元樹編碼成 N 叉樹
UndirectedGraphNode decode(TreeNode root)

主要思路

N 叉樹編碼成二元樹的方法是將 N 叉樹中每個節點的子節點轉換成自己左樹的右邊界或者右樹的左邊界，範例圖如下

二元樹編碼成 N 叉樹的方法就是把每個節點的左樹右邊界存到一個 List 裡面，作為這個節點的子節點列表即可，就是上述範例圖的逆過程。

N 叉樹編碼成二元樹的過程就是一個深度優先遍歷，首先

TreeNode head = new TreeNode(root.label);

表示二元樹的根節點就是 N 叉樹的根節點，

然後將根節點的孩子節點，呼叫遞迴，進行深度優先遍歷，程式碼如下

// 將某個節點的孩子節點掛在其右樹的左邊界上
// 將 N 叉樹的根節點的孩子節點做深度優先遍歷
// 並將其掛在根節點的右樹上
head.right = en(root.neighbors);

// 深度優先遍歷
private TreeNode en(List<UndirectedGraphNode> neighbors) {
        TreeNode c = null;
        TreeNode head = null;
        for (UndirectedGraphNode neighbor : neighbors) {
            TreeNode node = new TreeNode(neighbor.label);
            if (head == null) {
                // 頭節點為空，建出來
                head = node;
            } else {
                // 否則掛在當前節點的右樹的左邊界上
                c.left = node;
            }
            c = node;
            c.right = en(neighbor.neighbors);
        }
        return head;
}

將二元樹轉換成 N 叉樹的邏輯如下：

首先

UndirectedGraphNode node = new UndirectedGraphNode(root.val);

表示：N 叉樹的根節點也是二元樹的根節點。

接著呼叫遞迴，將二元樹的右樹構造出 N 叉樹當前節點的孩子節點。

// 將二元樹的右樹構造出 N 叉樹當前節點的孩子節點
node.neighbors = de(root.right);

public ArrayList<UndirectedGraphNode> de(TreeNode root) {
    ArrayList<UndirectedGraphNode> children = new ArrayList<>();
    while (root != null) {
        UndirectedGraphNode cur = new UndirectedGraphNode(root.val);
        cur.neighbors = de(root.right);
        children.add(cur);
        root = root.left;
    }
    return children;
}

其中 while 迴圈中就是不斷的把當前節點的左樹右邊界加入到一個 List 中，最後返回。

完整程式碼如下

public class Solution {
    public UndirectedGraphNode decode(TreeNode root) {
        if (root == null) {
            return null;
        }
        UndirectedGraphNode node = new UndirectedGraphNode(root.val);
        node.neighbors = de(root.right);
        return node;
    }

    public ArrayList<UndirectedGraphNode> de(TreeNode root) {
        ArrayList<UndirectedGraphNode> children = new ArrayList<>();
        while (root != null) {
            UndirectedGraphNode cur = new UndirectedGraphNode(root.val);
            cur.neighbors = de(root.right);
            children.add(cur);
            root = root.left;
        }
        return children;
    }

    // 每個子節點轉換成自己左樹的右邊界或者右樹的左邊界 + 深度優先遍歷
    // 編碼
    public TreeNode encode(UndirectedGraphNode root) {
        if (root == null) {
            return null;
        }
        TreeNode head = new TreeNode(root.label);
        // 右樹的左邊界
        head.right = en(root.neighbors);
        return head;
    }

    private TreeNode en(List<UndirectedGraphNode> neighbors) {
        TreeNode c = null;
        TreeNode head = null;
        for (UndirectedGraphNode neighbor : neighbors) {
            TreeNode node = new TreeNode(neighbor.label);
            if (head == null) {
                // 頭節點為空，建出來
                head = node;
            } else {
                // 否則掛在當前節點的右樹的左邊界上
                c.left = node;
            }
            c = node;
            c.right = en(neighbor.neighbors);
        }
        return head;
    }
}

本文涉及到的所有圖例見：二元樹與N叉樹的互相轉換

演演算法和資料結構筆記

將 N 叉樹編碼為二元樹

將 N 叉樹編碼為二元樹

題目描述

主要思路

更多