摘要：對(duì)于任一重合元素，保證所在兩個(gè)局部遍歷有序，保證實(shí)現(xiàn)整體遍歷有序重合元素所在局部局部全部有序，遍歷該元素并出棧局部未全部有序，將未有序局部元素全部入棧。

文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

二叉樹(shù)遍歷：按照既定序，對(duì)每個(gè)節(jié)點(diǎn)僅訪(fǎng)問(wèn)一次；
二叉樹(shù)非遞歸遍歷思想：參考這篇博文，核心思想是存在重合元素的局部有序保證整體有序，由于二叉樹(shù)的結(jié)構(gòu)特點(diǎn)，二叉樹(shù)中的每個(gè)節(jié)點(diǎn)（除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)）均屬于兩個(gè)局部的重合元素。對(duì)于任一重合元素，保證所在兩個(gè)局部遍歷有序，保證實(shí)現(xiàn)整體遍歷有序；

重合元素所在局部：

局部全部有序，遍歷該元素并出棧；

局部未全部有序，將未有序局部元素全部入棧。由于棧是LIFO，局部元素按照逆序入棧；

二叉樹(shù)節(jié)點(diǎn)TreeNode聲明

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

lintcode 二叉樹(shù)的前序遍歷

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            // 重合節(jié)點(diǎn)完成所有局部有序，彈出
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: right -> left -> root
                if (top.node.right != null) {
                    stack.push(new Pair(top.node.right, false));
                }               
                if (top.node.left != null) {
                    stack.push(new Pair(top.node.left, false));
                }
                stack.push(new Pair(top.node, true));
            }
        }
        return list;
    }
}

public class Solution {
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayListlist, TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        traverse(list, root.left);
        traverse(list, root.right);
    }
}

lintcode 二叉樹(shù)的中序遍歷

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: right -> root -> left
                if (top.node.right != null) {
                     stack.push(new Pair(top.node.right, false));
                }
                stack.push(new Pair(top.node, true));
                if (top.node.left != null) {
                     stack.push(new Pair(top.node.left, false));
                }
            }
        }
        return list;
    }
}

public class Solution {
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayListlist, TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(list, root.left);
        list.add(root.val);
        traverse(list, root.right);
    }
}

lintcode 二叉樹(shù)的后序遍歷

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: root -> right -> left
                stack.push(new Pair(top.node, true));
                if (top.node.right != null) {
                     stack.push(new Pair(top.node.right, false));
                }
                if (top.node.left != null) {
                     stack.push(new Pair(top.node.left, false));
                }
            }
        }

        return list;
    }
}

public class Solution {
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayList list, TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(list, root.left);
        traverse(list, root.right);
        list.add(root.val);
    }
}

lintcode 二叉樹(shù)的層序遍歷，BFS按層遍歷實(shí)現(xiàn)

public class Solution {
    public ArrayList> levelOrder(TreeNode root) {
        ArrayDeque queue = new ArrayDeque();
        ArrayList> list = new ArrayList>();
        if (root == null) {
            return list;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            int level = queue.size();
            ArrayList levelList = new ArrayList();
            // 按層BFS遍歷
            for (int i = 0; i < level; i++) {
                TreeNode head = queue.poll();
                levelList.add(head.val);
                if (head.left != null) {
                    queue.offer(head.left);
                } 
                if (head.right != null) {
                    queue.offer(head.right);
                }
            }
            list.add(levelList);
        }
        return list;
    }
}