Java迭代实现层序序列转N叉树及前序遍历输出问题排查

核心错误点 #

• 构建子节点时重复创建对象：将子节点加入父节点的children列表和加入待处理节点队列时，分别new了两个不同的Node对象，导致队列中取出的节点和树中实际存在的节点没有关联，后续给队列节点加子节点不会同步到树结构上

修正后核心代码（buildTree方法） #

public static Node buildTree(List<Integer> dataAsList){
    // 输入合法性校验
    if (dataAsList.isEmpty() || dataAsList.get(0) == null|| dataAsList.get(1) !=null){
        System.out.println ("Invalid data to construct a tree");
        return null;
    }
    Queue<Integer> dataAsQueue = new LinkedList<>();
    for (Integer data: dataAsList) {
        dataAsQueue.add(data);
    }
    Queue<Node> nodeQueue = new LinkedList<>();
    Node root = new Node(dataAsQueue.poll());
    dataAsQueue.poll(); // 弹出根节点后跟随的分隔null
    nodeQueue.add(root);
    Node parent = root;
    while (!dataAsQueue.isEmpty()) {
        Integer childInt= dataAsQueue.poll();
        if (childInt != null){
            // 只创建一次子节点对象，同时加入父节点列表和待处理队列
            Node childNode = new Node(childInt);
            parent.getChildren().add(childNode);
            nodeQueue.add(childNode);
        } else {
            // 遇到null说明当前父节点的所有子节点已处理完成，切换下一个父节点
            parent = nodeQueue.poll();
        }
    }
    return root;
}

完整可运行代码 #

package AllTree;

import java.util.*;

public class ListToNArrayTree {
    public static class Node{
        public int val;
        public ArrayList<Node> children = new ArrayList<>();
        public Node (int val){
            this.val = val;
        }
        public Node (int val, ArrayList<Node> children){
            this.val = val;
            this.children = children;
        }
        public String toString(){
            return " " + val;
        }
        public ArrayList<Node> getChildren() {
            return children;
        }
        public void setChildren(ArrayList<Node> children) {
            this.children = children;
        }
    }

    public static Node buildTree(List<Integer> dataAsList){
        if (dataAsList.isEmpty() || dataAsList.get(0) == null|| dataAsList.get(1) !=null){
            System.out.println ("Invalid data to construct a tree");
            return null;
        }
        Queue<Integer> dataAsQueue = new LinkedList<>();
        for (Integer data: dataAsList) {
            dataAsQueue.add(data);
        }
        Queue<Node> nodeQueue = new LinkedList<>();
        Node root = new Node(dataAsQueue.poll());
        dataAsQueue.poll();
        nodeQueue.add(root);
        Node parent = root;
        while (!dataAsQueue.isEmpty()) {
            Integer childInt= dataAsQueue.poll();
            if (childInt != null){
                Node childNode = new Node(childInt);
                parent.getChildren().add(childNode);
                nodeQueue.add(childNode);
            } else {
                parent = nodeQueue.poll();
            }
        }
        return root;
    }
    public static void main(String[] args){
        List<Integer> dataAsList = Arrays.asList(1, null, 2,3,4, null,5,6,null,7,8,null,9,10);
        System.out.println ("前序遍历结果：" + preorder(buildTree(dataAsList)));
    }

    public static List<Integer> preorder(Node root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        preorderhelper(root, res);
        return res;
    }
    private static void preorderhelper(Node root, LinkedList<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        if (root.children != null) {
            for (Node c : root.children) {
                preorderhelper(c, res);
            }
        }
    }
}

运行结果 #

输入序列[1, null, 2,3,4, null,5,6,null,7,8,null,9,10]的输出为[1, 2, 5, 6, 3, 7, 8, 4, 9, 10]，与预期结果一致。

内容的提问来源于stack exchange，提问作者Chris