二叉树非递归遍历——已通过LintCode

先序遍历

LintCode题目链接

public class Solution {
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        while(root != null || !stack.empty()){
            if(root == null){
                root = stack.peek();
                stack.pop();
            }else{
                result.add(root.val);
                if(root.right != null){
                    stack.push(root.right);
                }
                root = root.left;
            }
            
        }
        
        return result;
    }
}

中序遍历

LintCode题目链接

public class Solution {
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        if(root == null){
            return result;
        }
        
        while(root != null || !stack.empty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            
            if(!stack.empty()){
                root = stack.peek();
                result.add(root.val);
                stack.pop();
                root = root.right;
            }
        }
        return result;
    }
}

后序遍历

LintCode题目链接
由于在LintCode的代码里定义内部类会出现奇怪的问题，不得已使用了两个Stack。nodeStack用于存放树节点，flagStack用来存放对应节点是否为第一次访问。

public class Solution {
    
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
     
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Boolean> flagStack = new Stack<>();

        
        while(root != null || !nodeStack.empty()){
            while(root != null){
                nodeStack.push(root);
                flagStack.push(true);
                root = root.left;
            }
            
            if(!nodeStack.empty()){
                TreeNode node = nodeStack.peek();
                Boolean flag = flagStack.peek();
                
                if(flag){
                    flagStack.pop();
                    flagStack.push(false);
                    root = node.right;
                }else{
                    result.add(node.val);
                    nodeStack.pop();
                    flagStack.pop();
                    root = null;
                }
            }
        }
        return result;
        
    }
}

当做一个记录，如果大家需要解释思路的话，不妨留言，我再补上思路～