我在leecode刷题目过程中,测试案例成功了,但是提交解答就会出现这个问题,感觉我的数据都已经初始化过了 但是 就是不可以用。
题目:给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下:
[
[3],
[20,9],
[15,7]
]
java代码:
/**
- Definition for a binary tree node.
- public class TreeNode {
- int val;
- TreeNode left;
- TreeNode right;
- TreeNode(int x) { val = x; }
-
}
*/
class Solution {
public List> zigzagLevelOrder(TreeNode root) {
List re = new ArrayList();
Stack st1 = new Stack();
Stack st2 = new Stack();
if(root.left != null)
st1.push(root.left);
if(root.right != null)
st1.push(root.right);
List rr = new ArrayList();
rr.add(root.val);
re.add(rr);
int useL = 1;
while (!st1.isEmpty()||!st2.isEmpty()){
List rr2 = new ArrayList();
if (useL == 1){
while(!st1.isEmpty()){
TreeNode t = (TreeNode) st1.pop();
rr2.add(t.val);
if(t.right!=null){
st2.push(t.right);
}
if(t.left!=null){
st2.push(t.left);
}
}
useL = 0;
}
else{
while(!st2.isEmpty()){
TreeNode t = (TreeNode) st2.pop();
rr2.add(t.val);
if(t.left!=null){
st1.push(t.right);
}
if(t.right!=null){
st1.push(t.left);
}
}
useL = 1;
}
re.add(rr2);
}
return re;
}
public static int findDeep(TreeNode root,int deep){
if (root.left == null && root.right == null){
return deep;
}
if(root.left != null){
deep = findDeep(root.left, deep+1);
}
if(root.right != null){
deep = findDeep(root.right, deep+1);
}
return deep;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; this.left = null; this.right = null;}
}
结果:
Exception in thread "main" java.lang.NullPointerException
at Solution.zigzagLevelOrder(TreeNode.java:15)
at Driver.main(__Driver__.java:21)附带playground源码:
/* ----------------------------------- WARNING:
Your code may fail to compile
because it contains public class
declarations.
To fix this, please remove the
"public" keyword from your class
declarations.
*/
/**
- Definition for a binary tree node.
- public class TreeNode {
- int val;
- TreeNode left;
- TreeNode right;
- TreeNode(int x) { val = x; }
- } */ class Solution { public List> zigzagLevelOrder(TreeNode root) { List re = new ArrayList(); Stack st1 = new Stack(); Stack st2 = new Stack(); if(root.left != null) st1.push(root.left); if(root.right != null) st1.push(root.right); List rr = new ArrayList(); rr.add(root.val); re.add(rr); int useL = 1; while (!st1.isEmpty()||!st2.isEmpty()){ List rr2 = new ArrayList(); if (useL == 1){ while(!st1.isEmpty()){ TreeNode t = (TreeNode) st1.pop(); rr2.add(t.val); if(t.right!=null){ st2.push(t.right); } if(t.left!=null){ st2.push(t.left); } } useL = 0; } else{ while(!st2.isEmpty()){ TreeNode t = (TreeNode) st2.pop(); rr2.add(t.val); if(t.left!=null){ st1.push(t.right); } if(t.right!=null){ st1.push(t.left); } } useL = 1; } re.add(rr2); } return re; } public static int findDeep(TreeNode root,int deep){ if (root.left == null && root.right == null){ return deep; } if(root.left != null){ deep = findDeep(root.left, deep+1); } if(root.right != null){ deep = findDeep(root.right, deep+1); } return deep; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; this.left = null; this.right = null;} }
public class MainClass {
public static TreeNode stringToTreeNode(String input) {
input = input.trim();
input = input.substring(1, input.length() - 1);
if (input.length() == 0) {
return null;
}
String[] parts = input.split(",");
String item = parts[0];
TreeNode root = new TreeNode(Integer.parseInt(item));
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
int index = 1;
while(!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int leftNumber = Integer.parseInt(item);
node.left = new TreeNode(leftNumber);
nodeQueue.add(node.left);
}
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int rightNumber = Integer.parseInt(item);
node.right = new TreeNode(rightNumber);
nodeQueue.add(node.right);
}
}
return root;
}
public static String integerArrayListToString(List<Integer> nums, int length) {
if (length == 0) {
return "[]";
}
String result = "";
for(int index = 0; index < length; index++) {
Integer number = nums.get(index);
result += Integer.toString(number) + ", ";
}
return "[" + result.substring(0, result.length() - 2) + "]";
}
public static String integerArrayListToString(List<Integer> nums) {
return integerArrayListToString(nums, nums.size());
}
public static String int2dListToString(List<List<Integer>> nums) {
StringBuilder sb = new StringBuilder("[");
for (List<Integer> list: nums) {
sb.append(integerArrayListToString(list));
sb.append(",");
}
sb.setCharAt(sb.length() - 1, ']');
return sb.toString();
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = in.readLine()) != null) {
TreeNode root = stringToTreeNode(line);
List<List<Integer>> ret = new Solution().zigzagLevelOrder(root);
String out = int2dListToString(ret);
System.out.print(out);
}
}
}