[leetcode] 根据String数组构造TreeNode,用于LeetCode树结构相关的测试用例

时间:2024-08-30 17:07:02

LeetCode 跟树结构相关的题目的测试用例中大多是通过String数组来构造树。例如{2,#,3,#,4,#,5,#,6},可以构造出如下的树(将树结构逆时针选择90度显示):

6
            5
        4
    3
2

很直观地可以理解,输入的String数组是对树结构进行“层序”遍历得到的结果。以下代码用于构造树结构,并提供printTree用于打印树结构。

package util;

import java.util.LinkedList;
import java.util.Queue; public class util {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right; TreeNode(int x) {
val = x;
}
} /*
* construct TreeNode from a array format string, for test cases of LeetCode
*/
public static TreeNode createTree(String tree) {
// {1,2,3,4,#,#,#,5,#,6,#,7,#,8}
String[] ss = tree.split(",");
return createTree(ss);
} public static TreeNode createTree(String[] tree) {
Queue<TreeNode> q = new LinkedList<TreeNode>();
// 1st one should not be #
TreeNode root = constructOne(tree[0]);
q.add(root);
int idx = 1;
while (!q.isEmpty()) { TreeNode tn = q.poll();
if (tn == null) {
continue;
}
// construct tn's left&right node
// when to stop
if (idx == tree.length) {
break;
}
TreeNode left_ = constructOne(tree[idx]);
tn.left = left_;
q.add(left_);
idx++;
if (idx == tree.length) {
break;
}
TreeNode right_ = constructOne(tree[idx]);
idx++; tn.right = right_;
// add to queue
q.add(right_);
} return root; } private static void printNode(TreeNode tn, int indent) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indent; i++) {
sb.append("\t");
}
sb.append(tn.val);
System.out.println(sb.toString());
} public static void printTree(TreeNode root, int indent) {
if (root == null) {
return;
}
// if (root.left == null && root.right == null) {
// printNode(root, indent);
// }
// right
printTree(root.right, indent + 1);
// self
printNode(root, indent);
// left
printTree(root.left, indent + 1);
} public static void printTree(TreeNode root) {
// right first
printTree(root, 0);
} private static TreeNode constructOne(String s) {
if (s.compareTo("#") == 0) {
return null;
} else {
return new TreeNode(Integer.parseInt(s));
}
} public static void main(String args[]) {
TreeNode tn = createTree("2,#,3,#,4,#,5,#,6");
printTree(tn);
}
}