• 0

  • 471

[力扣刷题工具]数组(字符串)序列形式的二叉树转实体二叉树工具分享

3星期前

场景介绍

在力扣刷题的时候,对于参数输入是二叉树相关的题(例如下面的情况)

看似自己代码都对,就是执行不出预期结果,而当我想要把代码放到idea里面调试的时候,问题就来了。TM,难道我要人工根据这个二叉树序列手动构建一棵实例二叉树吗?

身为程序员,当然是选择让程序帮我们解决,于是乎,我就写了个LeetCode上的序列二叉树(字符串)转实体二叉树的工具类,方便以后调试使用。

不想了解原理和实现细节的话,直接到第三部分代码实现,拷走代码即可使用。

原理

原理其实很简单,就是根据序列二叉树,递归的转成一棵实体树。但是其中有几个点是需要注意的:

  1. LeetCode上面给出的,我们能用的,就是一串字符串,应该怎么转换成数组?
  2. LeetCode上的空节点是"null",应该怎么处理呢?
  3. LeetCode上给出的二叉树序列并不是满二叉树,而我们构建实体二叉树的时候,需要用满二叉树,如何转换为满二叉树?

1. 字符串二叉树序列转成数组二叉树序列

/**
* 将LeetCode给出的字符串二叉树拆分,转为以节点为单位的List
* @param array 例如:"[10,5,-3,3,2,null,11,3,-2,null,1]"
* @return
*/
private static ArrayList<Integer> stringToArray(String array) throws Exception {
  ArrayList<Integer> list = new ArrayList<>();
  // 将头和尾的 "[]" 去除
  String temp = array.substring(1, array.length() - 1);
  // 根据","划分字符串为子字符串。
  String[] strings = temp.split(",");

  for (String s : strings) { // 对于每个子字符串,如果能转成int,就加入,否则加入null
    Integer num = null;
    try {
      num = Integer.parseInt(s);
    } catch (Exception e) {
    } finally {
      list.add(num);
    }
  }
  return list;
}
复制代码

此处因为是自己使用,并没有考虑异常处理。正常使用是没问题的。

2. 添加缺失的null值,将其转为满二叉树序列

private static void addMissingNull (List<Integer> list) {
  int listInitSize = list.size();
  int addCount = 0;
  //listInitSize + addCount 表示初始数组加上当前额外加的null的个数
  for(int i = 0; i < listInitSize + addCount; i++) {
    if(null == list.get(i)) {
      if((i + 1) * 2 - 1 < listInitSize + addCount) {
        list.add((i + 1) * 2 - 1, null);
        addCount++;
      }
      if((i + 1) * 2  < listInitSize + addCount) {
        list.add((i + 1) * 2, null);
        addCount++;
      }
    }
  }
}
复制代码

3. 根据满二叉树序列递归构建实体二叉树

public static TreeNode arrayToTree (ArrayList<Integer> array) {
  return arrayToTreeRecursion(array, 1);
}
private static TreeNode arrayToTreeRecursion(ArrayList<Integer> array, int index) {
  if (index > array.size() || null == array.get(index - 1)) return null;

  TreeNode node = new TreeNode(array.get(index - 1));
  node.left = arrayToTreeRecursion(array, index * 2);
  node.right = arrayToTreeRecursion(array, index * 2 + 1);
  return node;
}
复制代码

测试

拿去用吧!

public class Tools {
    /**
     * demo
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        // 测试LeetCode字符串树转实体树
        String array = "{5,4,8,11,null,13,4,7,2,null,null,5,1}";
        TreeNode root = stringToTree(array);
        printTree(root);
    }

    /**
     * LeetCode字符串形式的树,转换为树实体
     * @param array 例如:[4,5,null,7] or {4,5,null,7}
     * @return
     * @throws Exception
     */
    public static TreeNode stringToTree (String array) throws Exception {
        ArrayList<Integer> list = stringToArray(array);
        addMissingNull(list);
        return arrayToTree(list);
    }

    /**
     * 根据给出的满二叉树List,转成实体树
     * @param array
     * @return
     */
    public static TreeNode arrayToTree (ArrayList<Integer> array) {
        return arrayToTreeRecursion(array, 1);
    }

    /**
     * 根据满二叉树的顺序数组,递归构建二叉树。
     * @param array
     * @param index
     * @return
     */
    private static TreeNode arrayToTreeRecursion(ArrayList<Integer> array, int index) {
        if (index > array.size() || null == array.get(index - 1)) return null;

        TreeNode node = new TreeNode(array.get(index - 1));
        node.left = arrayToTreeRecursion(array, index * 2);
        node.right = arrayToTreeRecursion(array, index * 2 + 1);
        return node;
    }

    /**
     * 将LeetCode给出的字符串二叉树拆分,转为以节点为单位的List
     * @param array
     * @return
     */
    private static ArrayList<Integer> stringToArray(String array) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();
        String temp = array.substring(1, array.length() - 1);
        String[] strings = temp.split(",");

        for (String s : strings) {
            Integer num = null;
            try {
                num = Integer.parseInt(s);
            } catch (Exception e) {
            } finally {
                list.add(num);
            }
        }
        return list;
    }

    /**
     * 因为LeetCode给出的字符串数据,在第一个节点为null时,此null节点的子节点就不再字符串中出现了
     * 而我们需要用于构建二叉树的数组,是满的二叉树,即使null子节点也为null,要体现在数组中。
     * 所以,此函数用于添加在LeetCode字符串中缺失的null
     * @param list
     */
    private static void addMissingNull (List<Integer> list) {
        int listInitSize = list.size();
        int addCount = 0;
        //listInitSize + addCount 表示初始数组加上当前额外加的null的个数
        for(int i = 0; i < listInitSize + addCount; i++) {
            if(null == list.get(i)) {
                if((i + 1) * 2 - 1 < listInitSize + addCount) {
                    list.add((i + 1) * 2 - 1, null);
                    addCount++;
                }
                if((i + 1) * 2  < listInitSize + addCount) {
                    list.add((i + 1) * 2, null);
                    addCount++;
                }
            }
        }
    }

    /**
     * 前序遍历打印一棵二叉树
     * @param root
     */
    public static void printTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        recursion(root, list);
        for (TreeNode node : list) {
            System.out.print(node.val + ",");
        }
        System.out.println();

    }

    /**
     * 前序遍历,加入List
     * @param root
     * @param list
     */
    private static void recursion(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        list.add(root);
        recursion(root.left, list);
        recursion(root.right, list);
    }
}
复制代码

感谢观看!若有什么错误,欢迎指正!

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

程序员

471

相关文章推荐

未登录头像

暂无评论