如何从级别顺序遍历字符串构造二叉树 [英] How to construct a binary tree from just the level order traversal string

问题描述

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

Consider a binary tree with the following properties:

1. 内部节点（非叶节点）的值为1（如果有）两个孩子。


2. 叶子节点的值为0，因为它没有子节点。

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

A level order traversal on the tree would generate a string of 1s and 0s (by printing the weird value at each node as they are visited). Now given this string construct the binary tree and perform a post order traversal on the tree. The post order string should be the output of the program.

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

For example: Input String is 111001000. Create a binary tree from this. Then perform the post order traversal on the tree which would result in an output: 001001011

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

The "crux" of the problem is to create the binary tree from just the level order string. How would I do this?

推荐答案

我认为概念上更简单。

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

这篇关于如何从级别顺序遍历字符串构造二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！