144. Binary Tree Preorder Traversal(二叉树的前序遍历)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/classSolution {
publicList<Integer>preorderTraversal(TreeNoderoot) {
List<Integer>list=newArrayList<>();
Stack<TreeNode>stack=newStack<>();
while (root!=null||!stack.isEmpty()) {
while (root!=null) {
stack.push(root);
list.add(root.val);
root=root.left;
            }
root=stack.pop();
root=root.right;
        }
returnlist;
    }
}

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/classSolution {
publicList<Integer>preorderTraversal(TreeNoderoot) {
List<Integer>list=newArrayList<>();
preorder(list, root);
returnlist;
    }
publicvoidpreorder(List<Integer>list, TreeNoderoot) {        
if (root==null) {
return ;
        }
list.add(root.val);
preorder(list, root.left);
preorder(list, root.right);
    }
}

/* -----------------------------------*  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; }* }*/classSolution {
publicList<Integer>preorderTraversal(TreeNoderoot) {
List<Integer>list=newArrayList<>();
preorder(list, root);
returnlist;
    }
publicvoidpreorder(List<Integer>list, TreeNoderoot) {        
if (root==null) {
return ;
        }
list.add(root.val);
preorder(list, root.left);
preorder(list, root.right);
    }
}
publicclassMainClass {
publicstaticTreeNodestringToTreeNode(Stringinput) {
input=input.trim();
input=input.substring(1, input.length() -1);
if (input.length() ==0) {
returnnull;
        }
String[] parts=input.split(",");
Stringitem=parts[0];
TreeNoderoot=newTreeNode(Integer.parseInt(item));
Queue<TreeNode>nodeQueue=newLinkedList<>();
nodeQueue.add(root);
intindex=1;
while(!nodeQueue.isEmpty()) {
TreeNodenode=nodeQueue.remove();
if (index==parts.length) {
break;
            }
item=parts[index++];
item=item.trim();
if (!item.equals("null")) {
intleftNumber=Integer.parseInt(item);
node.left=newTreeNode(leftNumber);
nodeQueue.add(node.left);
            }
if (index==parts.length) {
break;
            }
item=parts[index++];
item=item.trim();
if (!item.equals("null")) {
intrightNumber=Integer.parseInt(item);
node.right=newTreeNode(rightNumber);
nodeQueue.add(node.right);
            }
        }
returnroot;
    }
publicstaticStringintegerArrayListToString(List<Integer>nums, intlength) {
if (length==0) {
return"[]";
        }
Stringresult="";
for(intindex=0; index<length; index++) {
Integernumber=nums.get(index);
result+=Integer.toString(number) +", ";
        }
return"["+result.substring(0, result.length() -2) +"]";
    }
publicstaticStringintegerArrayListToString(List<Integer>nums) {
returnintegerArrayListToString(nums, nums.size());
    }
publicstaticvoidmain(String[] args) throwsIOException {
BufferedReaderin=newBufferedReader(newInputStreamReader(System.in));
Stringline;
while ((line=in.readLine()) !=null) {
TreeNoderoot=stringToTreeNode(line);
List<Integer>ret=newSolution().preorderTraversal(root);
Stringout=integerArrayListToString(ret);
System.out.print(out);
        }
    }
}