昨晚中興筆試題，第一題是給定二叉樹(shù)，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是 value,left,right，比較根節(jié)點(diǎn)到各個(gè)葉子節(jié)點(diǎn)路徑和的大小，輸出路徑和的最小值。(補(bǔ)充：用ArrayList可以存儲(chǔ))
以前沒(méi)做過(guò)關(guān)于樹(shù)的題，所以沒(méi)想到如何處理各個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)，即不會(huì)遍歷二叉樹(shù)，在這里做一個(gè)總結(jié)
1.遞歸實(shí)現(xiàn)遍歷

//遞歸實(shí)現(xiàn)遍歷，各種不同的遍歷實(shí)際上是輸出的位置不同，但是都是遞歸
//先序遍歷，傳入 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.非遞歸實(shí)現(xiàn)遍歷
非遞歸實(shí)現(xiàn)遍歷，用到棧來(lái)存儲(chǔ)路徑，輸出路徑

//先序遍歷1，傳入t =root1
public void iteratorPre(Node t){
  Stack<Node> stack = new Stack<Node>();
  stack.push(t);
  //每次取出節(jié)點(diǎn)的順序總是根，左，右
  while(!stack.Empty()){
  t = stack.pop();
  System.out.println(t.getValue());
  //先壓入右節(jié)點(diǎn)，再壓入左節(jié)點(diǎn)，因?yàn)闂Ｊ窍冗M(jìn)后出的
  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) {//壓入所有的左節(jié)點(diǎn)，壓入前訪問(wèn)它  
                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) {  
            //壓入根節(jié)點(diǎn)和左節(jié)點(diǎn)
            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.計(jì)算所有路徑中的最小值

import java.util.;
public class Main{
/來(lái)源：
* 中興機(jī)試題：計(jì)算二叉樹(shù)根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最短路徑
* 注意：為了記錄路徑，用棧，找到葉子節(jié)點(diǎn)后計(jì)算，然后pop()出去，再找下一個(gè)
* */
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));
        }
}
     //遞歸實(shí)現(xiàn)，每當(dāng)發(fā)現(xiàn)葉子節(jié)點(diǎn)，就計(jì)算一次
 public static void findMin(Node t,Stack<Node> n){
     if(t == null)
         return;
     n.push(t);
     //t是葉子節(jié)點(diǎn),此時(shí)計(jì)算路徑和
     if(t.getLeft() == null && t.getRight() == null){

         int sum =0;
                     //clone()方法，避免修改原來(lái)的棧
         Stack<Node> s1= (Stack<Node>)n.clone();
         for(int j =0;j < n.size();j++){
             sum += s1.pop().getValue();
         }
         list.add(sum);
                     //去除葉子節(jié)點(diǎn)
         n.pop();
     }else{
                             //遞歸尋找
             findMin(t.getLeft(),n);
             findMin(t.getRight(),n);
                             //經(jīng)過(guò)該節(jié)點(diǎn)的路徑已找完，刪除該節(jié)點(diǎn)
             n.pop();
     }   
 }
 public static void pre(Node t){
     if(t == null)
     return;
     System.out.println(t.getValue());
     pre(t.getLeft());
     pre(t.getRight());
 }

}

//節(jié)點(diǎn)結(jié)構(gòu)
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;

}