java 通过字符串建立二叉树
package mian.erchashu; /** * 给定字符串建立二叉树 空节点用null表示 * * @author xuminggang * */ public class StringToBinaryTree { public static void main(String[] args) { TreeNode root = stringToTree("[3,9,20,2,null,15,7]"); new StringToBinaryTree().preOrder(root); } public static TreeNode stringToTree(String str) { String[] elems = stringToArray(str); if (null == elems) { return null; } TreeNode root = createTree(elems, 0); return root; } /** * 递归构建二叉树 * * @param arr * @param index * @return */ private static TreeNode createTree(String[] arr, int index) { TreeNode tn = null; if (index < arr.length) { if (arr[index].equals("null")) { return null; } Integer val = Integer.valueOf(arr[index]); tn = new TreeNode(val); // 构建二叉树左子树 tn.left = createTree(arr, 2 * index + 1); // 构建二叉树右子树 tn.right = createTree(arr, 2 * index + 2); } return tn; } private static String[] stringToArray(String str) { if (null != str && str.equals("")) { return null; } String[] fields = str.split(","); fields[0] = fields[0].substring(1); int lastIndex = fields.length - 1; fields[lastIndex] = fields[lastIndex].substring(0, 1); return fields; } public void preOrder(TreeNode root) { if (root == null) { return; } System.out.println(root.val); preOrder(root.left); preOrder(root.right); } } class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } }
下一篇:
算法练习----青蛙跳台阶