如何仅从级别顺序遍历字符串构造二叉树

debugcn 发表于 Dev

金森·乔治（Jinson George）

考虑具有以下属性的二叉树：

如果内部节点（非叶节点）有两个子节点，则其值为1。
叶子节点没有子节点，因此其值为0。

在树上进行级别顺序遍历将生成1和0的字符串（通过在访问它们时在每个节点上打印怪异值）。现在给定该字符串，构造二叉树并在该树上执行后顺序遍历。后订单字符串应为程序的输出。

例如：输入字符串为111001000。由此创建一个二叉树。然后在树上执行后顺序遍历，这将导致输出：001001011

问题的“关键点”是仅从级别顺序字符串创建二叉树。我该怎么做？

金森·乔治（Jinson George）

我认为从概念上讲更简单。

import java.util.LinkedList;
import java.util.Queue;

class WeirdBinaryTree
{
static class Node
{
    private Node right;
    private Node left;
    private int weirdValue;

    public void setWeirdValue(int value)
    {
        weirdValue=value;
    }
}

private static Node makeTree(String str)throws Exception
{
    char[] array=str.toCharArray();
    Node root=new Node();
    Queue<Node> list=new LinkedList();
    list.add(root);
    int i=0;
    Queue<Node> nextList=new LinkedList<Node>();
    while(!list.isEmpty())
    {
        if(array[i++]=='1')
        {                
                Node temp=list.poll();
                temp.left=new Node();
                temp.right=new Node();
                temp.setWeirdValue(1);
                nextList.add(temp.left);
                nextList.add(temp.right);       
        }
        else
        {
            list.poll();
        }
        if(list.isEmpty())
        {
            list=nextList;
            nextList=new LinkedList<Node>();
        }
    }
    return root;
}

private static void postTraversal(Node localRoot)
{
    if(localRoot!=null)
    {
        postTraversal(localRoot.left);
        postTraversal(localRoot.right);
        System.out.print(localRoot.weirdValue);
    }
}

public static void main(String[] args)throws Exception 
{
    postTraversal(makeTree("111001000"));
}
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。