將 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叉樹的互相轉換

算法和數據結構筆記

Tags: LintCode 二叉樹數據結構算法算法和數據結構