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

Question

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

1. 如果内部节点(非叶节点)有两个子节点,则其值为1.
2. 叶节点的值为0,因为它没有子节点.

树上的级别顺序遍历将生成1和0的字符串(通过在访问每个节点时打印奇怪的值).现在给定此字符串构造二叉树并在树上执行post order遍历.后订单字符串应该是程序的输出.

例如:输入字符串是111001000.从中创建二叉树.然后在树上执行post order遍历,这将导致输出:001001011

问题的"症结"是仅从级别顺序字符串创建二叉树.我该怎么做？

Answer 1

我认为概念上更简单。

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"));
}
}