已知二叉树层次遍历字符串和子节点数，求二叉树

Question

 //输入参数为广度优先算法遍历的二叉树字符串LIST，每个节点对应子节点数LIST。 
   // 
  public static TreeNode<String> rebuildFromBFSList(List<String> bfsData, List<Integer> childCounts) 
  { 
    // TODO: your code for part (b) 
    return null; 
  } bfsData  A B C D E F G 
childCounts  6 4 0 0 2 0 0 
    //       A 
    //      / \ 
    //     B   C 
    //    / \ 
    //   D   E 
    //      / \ 
    //     F   G 
示例数据如上图所示，求解，不胜感激。 

Answer 1

请问你这个TreeNode是什么样的结构？

Answer 2

package com.suen;public class Node {
private Node left;
private Node right;
private String name;
private int childs; public Node() { } public Node(String name) {
this();
this.name = name;
} public Node(String name, int childs) {
this(name);
this.childs = childs;
} public Node getLeft() {
return left;
} public void setLeft(Node left) {
this.left = left;
} public Node getRight() {
return right;
} public void setRight(Node right) {
this.right = right;
} public String getName() {
return name;
} public void setName(String name) {
this.name = name;
} public int getChilds() {
return childs;
} @Override
public String toString() {
return "[name:" + name + ",childs:" + childs + "]";
} public void print(boolean isRoot, String strPreParent, Node parent) {
String subPreString = "";
String currentPrev = "";
if (isRoot) {
System.out.println(name);
if (this.left != null && this.right != null) {
this.left.print(false, subPreString, this);
this.right.print(false, subPreString, this);
}
} else {// ┠┃┗
if (parent.left == this) {
currentPrev = "┠";
subPreString = "┃";
} else if (parent.right == this) {
currentPrev = "┗";
subPreString = "　";
}

System.out.println(strPreParent + currentPrev + name);
if (this.left != null && this.right != null) {
subPreString = strPreParent + subPreString;
this.left.print(false, subPreString, this);
this.right.print(false, subPreString, this);
}
}
}}package com.suen;import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;public class BFS_Recover {
/**
 * @param bfsData
 * @param childCounts
 * @return
 */
public static Node rebuildFromBFSList(List<String> bfsData,
List<Integer> childCounts) {
List<Node> nodes = new ArrayList<Node>();
for (String s : bfsData) {
Node node = new Node(s, childCounts.get(bfsData.indexOf(s)));
System.out.println(node.getName() + "\t" + node.getChilds());
nodes.add(node);
}
List<Node> parentTempNodeList = new ArrayList<Node>();
List<Node> subTempNodeList = new ArrayList<Node>();
List<Node> exchangeNodeList = new ArrayList<Node>();
Node root = nodes.get(0);
parentTempNodeList.add(root);
nodes.remove(0); do {
int cnt = 0;
for (int i = 0; i < parentTempNodeList.size(); i++) {
Node node = parentTempNodeList.get(i);
if (node.getChilds() >= 2) {
cnt += 2;
}
} for (int i = 0; i < cnt; i++) {
subTempNodeList.add(nodes.get(0));
nodes.remove(0);
}
exchangeNodeList = null;
exchangeNodeList = Arrays.asList(subTempNodeList
.toArray(new Node[] {}));
for (int i = 0; i < parentTempNodeList.size(); i++) {
Node node = parentTempNodeList.get(i);
if (node.getChilds() >= 2) {
node.setLeft(subTempNodeList.get(0));
node.setRight(subTempNodeList.get(1));
subTempNodeList.remove(0);
subTempNodeList.remove(0);
}
}
subTempNodeList.clear();
parentTempNodeList = Arrays.asList(exchangeNodeList
.toArray(new Node[] {}));
} while (nodes.size() > 0);
return root;
} public static void main(String[] args) {
List<String> bfsData = new ArrayList<String>();
List<Integer> childCounts = new ArrayList<Integer>(); bfsData.add("A");
bfsData.add("B");
bfsData.add("C");
bfsData.add("D");
bfsData.add("E");
bfsData.add("F");
bfsData.add("G");
childCounts.add(6);
childCounts.add(4);
childCounts.add(0);
childCounts.add(0);
childCounts.add(2);
childCounts.add(0);
childCounts.add(0);
Node root = rebuildFromBFSList(bfsData, childCounts);
System.out.println();
root.print(true, "", null);
}
}
A 6
B 4
C 0
D 0
E 2
F 0
G 0A
┠B
┃┠D
┃┗E
┃　┠F
┃　┗G
┗C