題目

用非遞歸版本完成。

程序核心思想

遞歸版很簡單，這里用非遞歸版本實(shí)現(xiàn)了一下。

• 前序遍歷
  前序遍歷需要一個(gè)棧。首先壓入頭結(jié)點(diǎn)（為空就返回list），判斷如果棧非空，那么出棧一個(gè)元素，把這個(gè)元素的值加到list中，如果這個(gè)節(jié)點(diǎn)的右孩子不是null，那么壓入右孩子，如果這個(gè)節(jié)點(diǎn)的左孩子不是null，那么壓入左孩子。然后檢查棧是不是非空，如此循環(huán)。知道棧空了，那么返回list。
• 中序遍歷
  中序遍歷也需要一個(gè)棧。中序遍歷的循環(huán)條件不太一樣，是如果棧不是空的或者當(dāng)前節(jié)點(diǎn)不為null，則繼續(xù)這個(gè)循環(huán)。這個(gè)循環(huán)是：如果當(dāng)前節(jié)點(diǎn)不是null，那么當(dāng)前節(jié)點(diǎn)入棧，并且當(dāng)前節(jié)點(diǎn)的指針指向當(dāng)前節(jié)點(diǎn)的左孩子，意思是如果當(dāng)前節(jié)點(diǎn)有左孩子，那么左孩子也入棧，直到當(dāng)前節(jié)點(diǎn)為空。這是出棧一個(gè)元素，把這個(gè)元素的值加入list，然后當(dāng)前節(jié)點(diǎn)的指針指向出棧元素的右孩子，然后繼續(xù)這個(gè)循環(huán)（判斷棧非空或者當(dāng)前節(jié)點(diǎn)不為null，當(dāng)前節(jié)點(diǎn)及左孩子入棧...）
• 后序遍歷
  后序遍歷是左右中，所以可以把它放到一個(gè)棧里面，里面的元素順序?yàn)橹杏易螅@個(gè)結(jié)構(gòu)可以對比著前序遍歷（中左右）來改，然后該把值存到list中的時(shí)候，先存在stack中，等到全部元素進(jìn)stack之后，在從棧中彈元素，依次進(jìn)入list，順序就為左右中了。

Tips

代碼

//前序遍歷
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Stack;
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null)    return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        
        while(!stack.empty()){
            TreeNode cur = stack.pop();
            list.add(cur.val);
            if(cur.right != null)   stack.push(cur.right);
            if(cur.left != null)    stack.push(cur.left);
        }
        return list;
        
    }
}

//中序遍歷
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        while(!stack.empty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                TreeNode cur = stack.pop();
                list.add(cur.val);
                root = cur.right;
            }
        }
        return list;
    }
}

//后序遍歷
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<Integer> stack2 = new Stack<Integer>();
        List<Integer> list = new ArrayList<Integer>();
        
        if(root != null){
            stack1.push(root);
        }else{
            return list;
        }
        
        while(!stack1.empty()){
            TreeNode cur = stack1.pop();
            stack2.push(cur.val);
            if(cur.left != null)    stack1.push(cur.left);
            if(cur.right != null)   stack1.push(cur.right);
        }
        
        while(!stack2.empty()){
            list.add(stack2.pop());
        }
        
        return list;
        
    }
}