144.94.145 二叉树的前序、中序、后序遍历

题目

用非递归版本完成。

程序核心思想

递归版很简单，这里用非递归版本实现了一下。

• 前序遍历
  前序遍历需要一个栈。首先压入头结点（为空就返回list），判断如果栈非空，那么出栈一个元素，把这个元素的值加到list中，如果这个节点的右孩子不是null，那么压入右孩子，如果这个节点的左孩子不是null，那么压入左孩子。然后检查栈是不是非空，如此循环。知道栈空了，那么返回list。
• 中序遍历
  中序遍历也需要一个栈。中序遍历的循环条件不太一样，是如果栈不是空的或者当前节点不为null，则继续这个循环。这个循环是：如果当前节点不是null，那么当前节点入栈，并且当前节点的指针指向当前节点的左孩子，意思是如果当前节点有左孩子，那么左孩子也入栈，直到当前节点为空。这是出栈一个元素，把这个元素的值加入list，然后当前节点的指针指向出栈元素的右孩子，然后继续这个循环（判断栈非空或者当前节点不为null，当前节点及左孩子入栈...）
• 后序遍历
  后序遍历是左右中，所以可以把它放到一个栈里面，里面的元素顺序为中右左，这个结构可以对比着前序遍历（中左右）来改，然后该把值存到list中的时候，先存在stack中，等到全部元素进stack之后，在从栈中弹元素，依次进入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;
        
    }
}