请教用 Java 如何写一个用来将 leetcode 上给出的[4,1,null,2,null,3]这种形式的树，转换为一颗真的树的根节点的函数？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1666 天前的主题，其中的信息可能已经有所发展或是发生改变。

看似是层次遍历，但实际不是，不是之处在于，比如这颗树深度有 4 层，但第二层（共 2 个节点）中右边那个节点为 null，那显然这个节点的第三层的两个子节点也为 null，但层次遍历中这两个 null 是会出现的，而这种形式里不会出现。

我的想法是用队列往里放 node.left node.right 跟着这个形式，但遇到的问题是 Java 是值传递且没有引用传递的方式（吗？），因而往队列里放 node.left 再取出后，实际上没能改到 node.left 。。

谢谢

第 1 条附言 · 2020-04-14 19:44:43 +08:00

给出一个我的实现，目前用了几个都对~

    public static TreeNode build(Integer[] vals) {
        int valid_vals_size = vals.length;
        Queue<TreeNode> queue = new LinkedList<>();
        LinkedList<Integer> level_order_traveresal =
                new LinkedList<>(Arrays.asList(vals));
        TreeNode root = new TreeNode(vals[0]);
        queue.add(root);
        valid_vals_size--;

        int index = 0;
        while (true) {
            TreeNode poll = queue.poll();
            int left_index = 2 * index + 1;
            int right_index = 2 * index + 2;

            if (poll == null) {
                level_order_traveresal.add(left_index, null);
                level_order_traveresal.add(right_index, null);
            } else {
                if (left_index >= level_order_traveresal.size()) {
                    break;
                }
                Integer left_node = level_order_traveresal.get(left_index);
                if (left_node != null) {
                    poll.left = new TreeNode(left_node);
                    valid_vals_size--;
                }
                queue.add(poll.left);

                if (right_index >= level_order_traveresal.size()) break;
                Integer right_node = level_order_traveresal.get(right_index);
                if (right_node != null) {
                    poll.right = new TreeNode(right_node);
                    valid_vals_size--;
                }
                queue.add(poll.right);
            }

            index++;
            if (valid_vals_size <= 0) break;
        }
        return root;
    }

null

Node

节点

left

7 条回复 • 2020-04-14 20:41:35 +08:00

kkkkkrua

2020-04-14 18:43:29 +08:00

Java 是值传递且没有引用传递
反了吧？

kkkkkrua

2020-04-14 18:48:34 +08:00

@kkkkkrua #1 错了，看成了 C#的值类型，引用类型。。

forestn

2020-04-14 19:03:34 +08:00 via iPhone

深度优先递归吧？

Newyorkcity

2020-04-14 19:15:11 +08:00

@forestn 具体一些？

zmxnv123

2020-04-14 19:31:34 +08:00

用一个队列存放当前层的 Node.

luckyrayyy

2020-04-14 19:36:56 +08:00

没看懂你的意思，都为 null 了还便利他的子节点干啥？

xxdd

2020-04-14 20:41:35 +08:00

/**
* 10 0
* / \
* 5 -3 1-2
* / \ \
* 3 2 11 3-6
* / \ \
* 3 -2 1 7-14
*
* @param trees
* @return
*/
public static TreeNode initTreeNode(Integer[] trees, int n) {
if(n >= trees.length){
return null;
}
if(null == trees[n]) {
return null;
}
int l = n * 2 + 1;
if(l > trees.length){
return new TreeNode(trees[n],null,null);
}
TreeNode treeNode = new TreeNode(trees[n],initTreeNode(trees,2*n+1),initTreeNode(trees,2*n+2));
return treeNode;
}

public static void main(String[] args) {
Integer[] arr = {10, 5, -3, 3, 2, null, 11, 3, -2, null, 1};
TreeNode treeNode = initTreeNode(arr, 0);
}

以前写的一个工具类