求二叉树根节点到叶子节点路径和的最小值：遍历（递归+非递归）

昨晚中兴笔试题，第一题是给定二叉树，每个节点的数据结构是 value,left,right，比较根节点到各个叶子节点路径和的大小，输出路径和的最小值。(补充：用ArrayList可以存储)
以前没做过关于树的题，所以没想到如何处理各个节点的左右子节点，即不会遍历二叉树，在这里做一个总结
1.递归实现遍历

//递归实现遍历，各种不同的遍历实际上是输出的位置不同，但是都是递归
//先序遍历，传入 t = root1
public void preOrder(Node t){
  if(t == null)
  return;
  System.out.println(t.getValue());
  pre(t.getLeft());
  pre(t.getRight());
}
//中序遍历，传入 t = root1
public void inOder(Node t){
  if(t == null)
  return;
  inOrder(t.getLeft());
  System.out.println(t.getValue());
  inOrder(t.getRight());
}
//后序遍历，传入 t = root1
public void postOder(Node t){
  if(t == null)
  return;
  postOrder(t.getLeft());
  postOrder(t.getRight());
  System.out.println(t.getValue());

2.非递归实现遍历
非递归实现遍历，用到栈来存储路径，输出路径

//先序遍历1，传入t =root1
public void iteratorPre(Node t){
  Stack<Node> stack = new Stack<Node>();
  stack.push(t);
  //每次取出节点的顺序总是根，左，右
  while(!stack.Empty()){
  t = stack.pop();
  System.out.println(t.getValue());
  //先压入右节点，再压入左节点，因为栈是先进后出的
  if(t.getRight() != null)
  stack.push(t.getRight());
  if(t.getLeft() != null)
  stack.push(t.getLeft());
  }
}
//先序遍历2
 protected static void iterativePreorder2(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        Node node = p;  
        while (node != null || stack.size() > 0) {  
            while (node != null) {//压入所有的左节点，压入前访问它  
                visit(node);  
                stack.push(node);  
                node = node.getLeft();  
            }  
            if (stack.size() > 0) {//  
                node = stack.pop();  
                node = node.getRight();  
            }  
        }  
    }  
//中序遍历，传入 t = root1
  protected static void iterativeInorder(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        Node node = p;  
        while (node != null || stack.size() > 0) {  
            //压入根节点和左节点
            while (node != null) {  
                stack.push(node);  
                node = node.getLeft();  
            }  
            if (stack.size() > 0) {  
                node = stack.pop();  
                visit(node);  
                node = node.getRight();  
            }  
        }  
    } 
//后序遍历，单栈
  protected static void iterativePostorder3(Node p) {  
        Stack<Node> stack = new Stack<Node>();  
        Node node = p, prev = p;  
        while (node != null || stack.size() > 0) {  
            while (node != null) {  
                stack.push(node);  
                node = node.getLeft();  
            }  
            if (stack.size() > 0) {  
                Node temp = stack.peek().getRight();  
                if (temp == null || temp == prev) {  
                    node = stack.pop();  
                    visit(node);  
                    prev = node;  
                    node = null;  
                } else {  
                    node = temp;  
                }  
            }  
  
        }  
    }
3.计算所有路径中的最小值

import java.util.;
public class Main{
/来源：
* 中兴机试题：计算二叉树根节点到叶子节点的最短路径
* 注意：为了记录路径，用栈，找到叶子节点后计算，然后pop()出去，再找下一个
* */
static List<Integer> list = new ArrayList<Integer>();
public static void main(String[] args){
Node root1 = new Node();
Node node1 = new Node();
Node node2 = new Node();
Node node3 = new Node();
Node node4 = new Node();
Node node5 = new Node();
Node node6 = new Node();
root1.setLeft(node1);
root1.setRight(node2);
node1.setLeft(node3);
node1.setRight(node4);
node4.setLeft(node5);
node4.setRight(node6);

        root1.setValue(8);
        node1.setValue(8);
        node2.setValue(7);
        node3.setValue(9);
        node4.setValue(2);
        node5.setValue(4);
        node6.setValue(7);
        //先序遍历
        //pre(root1);
                    //用栈记录路径
        Stack<Node> n = new Stack<Node>();
        findMin(root1,n);
                     //list中是各条路径的和
        for(int i = 0;i < list.size();i++){
            System.out.println(list.get(i));
        }
}
     //递归实现，每当发现叶子节点，就计算一次
 public static void findMin(Node t,Stack<Node> n){
     if(t == null)
         return;
     n.push(t);
     //t是叶子节点,此时计算路径和
     if(t.getLeft() == null && t.getRight() == null){

         int sum =0;
                     //clone()方法，避免修改原来的栈
         Stack<Node> s1= (Stack<Node>)n.clone();
         for(int j =0;j < n.size();j++){
             sum += s1.pop().getValue();
         }
         list.add(sum);
                     //去除叶子节点
         n.pop();
     }else{
                             //递归寻找
             findMin(t.getLeft(),n);
             findMin(t.getRight(),n);
                             //经过该节点的路径已找完，删除该节点
             n.pop();
     }   
 }
 public static void pre(Node t){
     if(t == null)
     return;
     System.out.println(t.getValue());
     pre(t.getLeft());
     pre(t.getRight());
 }

}

//节点结构
class Node{
private int value;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
private Node left;
private Node right;

}