主页 / 问题 / 1247517
Accepted
A K
Asked:2022-02-23 10:50:53 +0000 UTC2022-02-23 10:50:53 +0000 UTC

将数组转换为二叉树

  • 772

我有一个代表二叉树的数字数组：

var data = new object[] { 1, 2, 3, 4, null, null, 5 };

我需要将其转换为经典形式：

在此处输入图像描述

（每个数字依次为中、左、右。如果为null，则跳过该节点）

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

我想出了一种能产生预期结果的构造方法：

private TreeNode CreateTree(object[] data)
{
    TreeNode[] nodes = data.Select(x => x == null ? null : new TreeNode((int)x, null, null)).ToArray();

    int current = 0;
    bool left = true;

    for (int i = 1; i < nodes.Length; i++)
    {
        if (left)
        {
            nodes[current].left = nodes[i];
            left = false;
        }
        else
        {
            nodes[current].right = nodes[i];
            left = true;

            current++;
            while (current < nodes.Length  && nodes[current] == null)
                current++;
        }
    }

    return nodes[0];
}

在此处输入图像描述

但在我看来，这是一种弯曲的自行车，您可以以某种方式更优雅地将宽度旁路（BFS / LOT）与深度旁路（DFS Preorder：中，左，右）结合起来。

有谁知道如何根据经典解决类似的问题？

c#

1 个回答

  1. Best Answer

    那么，有哪些选择？

    线路旁路（从末端）

    它类似于 BFS，只是相反。

    private TreeNode CreateTree(object[] data)
{
    var nodes = new Dictionary<int, TreeNode>();

    for (int i = data.Length - 1; i >= 0; i--)
    {
        object val = data[i];
        if (val == null) continue;
        int index = i + 1;

        nodes.TryGetValue(index * 2, out TreeNode left);
        nodes.TryGetValue(index * 2 + 1, out TreeNode right);

        var node = new TreeNode((int)val, left, right);
        nodes[index] = node;
    }

    nodes.TryGetValue(1, out TreeNode root);    
    return root;
}

    诀窍是bool left = true;您不需要这个，因为节点索引可以理解左节点或右节点。

    输出与您的相同。

    DFS 风格

    一个简单的递归。

    private TreeNode CreateTreeDFS(object[] data)
{
    return CreateTreeDFS(data, 0);
}

private TreeNode CreateTreeDFS(object[] data, int index)
{
    if (index < 0 || index >= data.Length) return null;
    
    var val = data[index];
    if (val == null) return null;
    
    return new TreeNode((int)val, CreateTreeDFS(data, (index + 1) * 2 - 1), CreateTreeDFS(data, (index + 1) * 2));
}

    输出与您的相同。

    bfs 风格

    最愚蠢的恕我直言，因为在通道之前有必要提前创建所有节点。

    private TreeNode CreateTreeBFS(object[] data)
{
    var nodes = new Dictionary<int, TreeNode>();

    for (int i = 0; i < data.Length; i++)
    {
        object val = data[i];
        if (val == null) continue;
        int index = i + 1;
        
        var node = new TreeNode((int)val, null, null);
        nodes[index] = node;
    }
    
    foreach(var key in nodes.Keys)
    {
        nodes.TryGetValue(key * 2, out TreeNode left);
        nodes.TryGetValue(key * 2 + 1, out TreeNode right);
        
        var node = nodes[key];
        node.left = left;
        node.right = right;
    }

    nodes.TryGetValue(1, out TreeNode root);
    return root;
}

    用于创建节点的 Linq 选项

    private TreeNode CreateTreeBFS(object[] data)
{
    var nodes = data.Select((v, ind) => (v, ind))
        .Where(x => x.v != null)
        .ToDictionary(x => x.ind +1, x => new TreeNode((int)x.v, null, null));

    foreach (var key in nodes.Keys)
    {
        nodes.TryGetValue(key * 2, out TreeNode left);
        nodes.TryGetValue(key * 2 + 1, out TreeNode right);

        var node = nodes[key];
        node.left = left;
        node.right = right;
    }

    nodes.TryGetValue(1, out TreeNode root);
    return root;
}

    输出与您的相同。

    • 4

相关问题