遍历思想：
前序遍历：根节点，左子树，右子树
中序遍历：左子树，根节点，右子树
后续遍历：左子树，右子树，根节点
层次遍历：按层顺序遍历即可
代码：
树结点：
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode（int x){
val = x;
}
}
1.1前序遍历（递归版）
public void preOrderTraverse1(TreeNode root){
if(root != null{
System.out.print(root.val + " ");
preOrderTraverse1(TreeNode root.left);
preOrderTraverse1(TreeNode root.right);
}
}
1.2 前序遍历（非递归版，迭代）
利用栈stack存储结点
public void preOrderTraverse2(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while(node != null || !stack.isEmpty()){
while(node != null){
System.out.print(node.val + " ");
stack.push(node);
node = node.left;
}
if(!stack.isEmpty()){
node = stack.pop();
node = node.right;
}
}
}
2.1中序遍历（递归版）
public void inOrderTraverse1(TreeNode root){
if(root != null{
inOrderTraverse1(TreeNode root.left);
System.out.print(root.val + " ");
inOrderTraverse1(TreeNode root.right);
}
}
2.2 中序遍历（非递归版）
利用栈stack存储结点
public void inOrderTraverse2(TreeNode root){
Stack stack = new Stack();
TreeNode node = root;
while(node != null || !stack.isEmpty()){
while(node != null){
stack.push(node);
node = node.left;
}
if(!stack.isEmpty()){
node = stack.pop();
System.out.print(node.val + " ");
node = node.right;
}
}
}
3.1后序遍历（递归版）
public void postOrderTraverse1(TreeNode root){
if(root != null{
preOrderTraverse2(TreeNode root.left);
preOrderTraverse2(TreeNode root.right);
System.out.print(root.val + " ");
}
}
3.2后序遍历（非递归法)
后序遍历与前序中序不一样，当后序遍历要保证输出当前结点时要保证左右子树都已经遍历完
设置一个lastVist游标
public static void postOrderTraverse2(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
TreeNode lastVisit = root;
while(node != null || !stack.isEmpty()){
whilee(node != null){
stack.push(node);
node = node.left;
}
node = stack.peek(); //查看当前栈顶元素
if(node.right == null || node.right == lastVisit){ //如果其右子树也为空，或者右子树已经访问，则可以直接输出当前结点的值
System.out.print(node.val + " ");
stack.pop();
lastVisit = node;
node = null;
}else{ //否则继续遍历右子树
node = node.right;
}
}
}
4. 层次遍历
利用队列
public void levelTraverse(TreeNode root){
if(root == null) return;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
