二叉树--序列化一棵树

今天学习的算法是最基础最常用的算法：序列化一棵树。

题目介绍

给定任意一个二叉树，将树以字符串方式输出，例如：

You may serialize the following tree:
    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

实现思路

先按个人的第一思考方案来实现：
1、先通过之前学习过的计算树的最大深度。
2、根据树的最大深度计算临时数组的长度，公式为：len = len + Math.pow(2,i)，其中i为所属层，根节点为第一层。
3、最后再按前序遍历的思想遍历树，并将树的值赋值到临时数组中，下标计算公式为：左子节点的index=当前节点的index2，右子节点的index=当前节点的index2+1。
4、最后只要再遍历数组，将数组转换成需要的String即可。

整个过程有一点点复杂的，明天再优化补充下思路图纸吧。

实现代码

public class SolutionCodec {

    public String serialize(TreeNode root) {
        if (null == root) {
            return "[]";
        }
        //通过树的最大高度计算数组长度，并初始化数组
        int len = len(root);
        String[] arr = new String[len];

        //将树转化为数组
        convert(root, 1, arr);

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 1; i < arr.length; i++) {

            if (null == arr[i]) {
                sb.append("null");
            } else {
                sb.append(arr[i]);
            }
            if (i < arr.length - 1) {
                sb.append(",")
            }
        }
        sb.append("]");

        return sb.toString();
    }

    private void convert(TreeNode node, int index, String[] arr) {
        if (null != node) {
            arr[index] = String.valueOf(node.val);
            convert(node.left, 2 * index, arr);
            convert(node.right, 2 * index + 1, arr);
        }
    }

    private int len(TreeNode root) {
        int depth = maxDepth(root);
        int i = 0;
        int len = 0;
        while (i++ < depth) {
            len = len + Double.valueOf(Math.pow(2, i)).intValue();
        }
        return len;
    }

    private int maxDepth(TreeNode root) {
        if (null == root) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        int maxDepth = Math.max(leftDepth, rightDepth) + 1;
        return maxDepth;
    }

    public TreeNode deserialize(String data) {
        return null;
    }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms