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

问题描述

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

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.

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

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

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