昨天做了个二叉树的笔试题大概十几分钟就做完了但是有些疑惑想到了一个新题不知道有没有人能解

下面是笔试题目: 根据用户的输入的字母, 构建一个满二叉树, 然后打印出它的所有从根到叶子的路径. (假设用户的输入字母的个数恰好满足构建一个满二叉树)
例如: 输入 a b c d e f g后构建成下面的树
a
b c
c d e f 就是这样的一个满二叉树

然后输出 abc，abd，ace，acf
要求: 使用任意一种你熟悉的语言即可。
然后菜鸟我是这样做的

/**
* Created by tangtang on 15/6/15.
*/
public class Tree {

public static void main(String[] args)
{
byte[] byteArray={'D','B','A','C','F','E','G'};

Node root=new Node();

for (byte b: byteArray)
{
root.insert(b);

}

root.traverseBiTree("");
}

static class Node{

private byte value=-1;

private Node leftChild;
private Node rightChild;

public Node getLeftChild()
{
return leftChild;
}

public Node getRightChild()
{
return rightChild;
}

public byte getValue()
{
return value;
}

public void setLeftChild(Node leftChild)
{
this.leftChild=leftChild;
}

public void setRightChild(Node rightChild)
{
this.rightChild=rightChild;
}

public void setValue(byte value)
{
this.value=value;
}

/**
* 遍历加打印遍历路径
* 思路让上一层都产生一个string
* @return
*/
public void traverseBiTree(String str)
{
str+=(char)value;
if (leftChild==null&&rightChild==null) {
System.out.println(str);
return;
}

if (leftChild!=null)
{
leftChild.traverseBiTree(str);
}

if (rightChild!=null)
{
rightChild.traverseBiTree(str);
}
}

public void insert(byte c)
{
if (value==-1) {
value = c;
return;
}

if (c>value)
{
if (rightChild==null)
rightChild=new Node();
rightChild.insert(c);
}else {
if (leftChild==null)
leftChild=new Node();
leftChild.insert(c);
}

}

}
}

用java写的有点长不过去掉set get方法也非常简洁了

在做的过程产生了这样一个问题
如果试题问的就是输入a b c d e f g 生成上边的那个满二叉树要求下一层的孩子都大于上一层的孩子并且右孩子都大于左孩子如何生成该上面的那个满二叉树？好好想想这个问题还是很困难的
要求只能一个一个的插入不可以先排序再生成二叉树

binux

2015-06-16 00:39:02 +08:00

@Heartwork

1、如果这么理解，这个题目是有问题的。
既然第 n 层全部大于第 n-1 层，「右孩子都大于左孩子」没有任何意义，在同一层之间交换元素，没有任何影响和副作用。那么这个「右孩子都大于左孩子」的要求，随便交换一下元素就可以了。

2、其次，这个问题不是完全排序的。
只要使用快速划分，让数组左边一半小于右边一半，然后对左边继续前面的过程。再加上1所诉的的交换元素，就可以建立起符合要求的树了。复杂度只有 O(n)

昨天做了个二叉树的笔试题 大概十几分钟就做完了 但是有些疑惑 想到了一个新题 不知道有没有人能解

昨天做了个二叉树的笔试题大概十几分钟就做完了但是有些疑惑想到了一个新题不知道有没有人能解