Java 一维数组转换二叉树结构

最近在 LeetCode 刷题，发现遇到不少二叉树类型的题目，题目会定义好树节点 TreeNode 的数据结构。

TreeNode

TreeNode 的数据结构如下：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

在题目的示例中，二叉树的输入都是一个一维数组，表示这个二叉树结构。

例如：

输入：root = [3,1,4,3,null,1,5]

表示的二叉树为：

因此在 IDE 里面编码调试时，需要一个转化方法方便自己编写并运行测试用例。

转换二叉树

一维数组转换二叉树结构：

public class TreeNodeUtil {
    /**
     * 一维数组转换二叉树结构
     * @param array
     * @return
     */
    public static TreeNode arrayToTreeNode(Integer[] array){
        if(array.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(array[0]);
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        boolean isLeft = true;
        for(int i = 1; i < array.length; i++){
            TreeNode node = queue.peek();
            if(isLeft){
                if(array[i] != null){
                    node.left = new TreeNode(array[i]);
                    queue.offer(node.left);
                }
                isLeft = false;
            }else {
                if(array[i] != null){
                    node.right = new TreeNode(array[i]);
                    queue.offer(node.right);
                }
                queue.poll();
                isLeft = true;
            }
        }
        return root;
    }
}

使用方式：

TreeNodeUtil.arrayToTreeNode(new Integer[]{2,null,4,9,8,null,null,4});

测试用例

表示二叉树

以下二叉树：

可以表示为：

TreeNodeUtil.arrayToTreeNode(new Integer[]{2,null,4,9,8,null,null,4});

测试二叉树

TreeNode p = new TreeNode(2,null,new TreeNode(4,new TreeNode(9),new TreeNode(8,new TreeNode(4),null)));
TreeNode q = TreeNodeUtil.arrayToTreeNode(new Integer[]{2,null,4,9,8,null,null,4});
System.out.println(TreeNodeUtil.isSameTree(p,q));

其中，isSameTree 方法如下：

public static boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null) {
        return p == q;
    }
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}