遞歸

比較簡(jiǎn)單,直接看代碼即可.

    private void preOrderRec(TreeNode node,ArrayList<Integer> pre){
        if(node==null) return;
        pre.add(node.val);
        preOrderRec(node.left,pre);
        preOrderRec(node.right,pre);
    }
    
    private void inOrderRec(TreeNode node,ArrayList<Integer> in){
        if(node==null) return;        
        inOrderRec(node.left,in);
        in.add(node.val);
        inOrderRec(node.right,in);
    }
    
    private void postOrderRec(TreeNode node,ArrayList<Integer> post){
        if(node==null) return; 
        postOrderRec(node.left,post);
        postOrderRec(node.right,post);
        post.add(node.val);
    }

非遞歸

先序遍歷

1. 申請(qǐng)一個(gè)棧,記為s1,將頭結(jié)點(diǎn)壓棧.
2. 每次從棧頂彈出節(jié)點(diǎn)node,打印node的值,如果node的右子節(jié)點(diǎn)不為空,壓棧.如果node的左子結(jié)點(diǎn)不為空,壓棧.
3. 重復(fù)步驟2直到棧為空.

//非遞歸版本
    private void preOrder(TreeNode node,ArrayList<Integer> pre){      
       Deque<TreeNode> stack=new ArrayDeque<TreeNode>();
       if(node==null) return;
       stack.push(node);
       while(!stack.isEmpty()){
           node=stack.pop();
           pre.add(node.val);
           if(node.right!=null)stack.push(node.right);
           if(node.left!=null)stack.push(node.left);           
       }
    }

中序遍歷

1. 申請(qǐng)一個(gè)棧,記為s1,當(dāng)前節(jié)點(diǎn)為node.
2. 將node及其左邊界壓入棧中,即不斷的利用node=node.left并對(duì)其壓棧,然后重復(fù)步驟2.
3. 直到node為空,此時(shí)從s1中彈出一個(gè)節(jié)點(diǎn),記為node,打印node的值并讓node=node.right.轉(zhuǎn)到步驟2.

 private void inOrder(TreeNode node,ArrayList<Integer> in){
        Deque<TreeNode> stack=new ArrayDeque<TreeNode>();
        while(node!=null||!stack.isEmpty()){    
           while(node!=null){
               stack.push(node);
               node=node.left;
           }      
           node=stack.pop();
           in.add(node.val);
           node=node.right;                       
       }        
    }

后序遍歷(兩個(gè)棧實(shí)現(xiàn))

1. 申請(qǐng)一個(gè)棧,記為s1,然后將頭結(jié)點(diǎn)壓入s1.
2. 從s1中彈出的節(jié)點(diǎn)記為node,先把node的左孩子壓入s1中,再把node的右孩子壓入s1中.
3. 在整個(gè)過(guò)程過(guò)程中,每個(gè)從s1中彈出的節(jié)點(diǎn)都?jí)喝氲絪2中.
4. 不斷重復(fù)2和3,直到s1為空.
5. 依次彈出s2的值就是后序遍歷的結(jié)果.

 private void postOrder(TreeNode node,ArrayList<Integer> post){
       Deque<TreeNode> stack1=new ArrayDeque<TreeNode>();
       Deque<TreeNode> stack2=new ArrayDeque<TreeNode>();
       if(node==null)return;
       stack1.push(node);
       while(!stack1.isEmpty()){
           node=stack1.pop();
           stack2.push(node);
           if(node.left!=null)stack1.push(node.left);
           if(node.right!=null)stack1.push(node.right);        
       }
       while(!stack2.isEmpty()){
           post.add(stack2.pop().val);
       }
    }