二叉树三种遍历递归及非递归实现&层次遍历(Java版)

二叉树基本概念
二叉树是每个结点至多有两颗子树的树，子树有左右之分，其次序不能任意颠倒。
几种特殊二叉树
1）满二叉树：高度为h，并且含有2^{h-1个结点的二叉树。即树的每一层都是满的（每层结点数为2}(h-1)）。若对满二叉树编号，从上自下，从左至右，根节点编号为1，则对于编号为i 的结点，如果有双亲，则双亲为⌊i/2⌋，如果有左孩子，左孩子为2i，如果有右孩子，右孩子为2i+1.如下图所示：

满二叉树.png

2）完全二叉树：若1个高度为h，含有n个结点的二叉树，按照从上自下，从左至右的顺序对结点进行编号，1~n的结点与满二叉树一一对应，则该二叉树为完全二叉树。如下图所示：

完全二叉树.png

3）二叉排序树：左子树上所有关键字均小于根节点关键字，右子树所有结点关键字均大于根节点关键字。左子树和右子树又各是一颗二叉排序树。
4）平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
二叉树遍历
二叉树定义

 public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

非递归实现借助栈，前序、中序、后序是相对于根节点而言，根据根节点输出的位置，根、左、右为前序遍历；左、根、右为中序遍历；左、右、根为后序遍历。
1）前序遍历(PreOrder)：
如果二叉树为空，则什么也不做；否则：
a)访问根节点；
b)先序遍历左子树；
c)先序遍历右子树。
递归实现：

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null)
        return list;
    helper(root, list);
    return list;
}
public void helper(TreeNode root, List<Integer> list) {
    list.add(root.val);
    if(root.left != null) 
        helper(root.left, list);
    if(root.right != null)
        helper(root.right, list);
}

常规版非递归实现：先将根节点入栈，然后弹出（访问根节点），然后将其右结点入栈，再将其左结点入栈（栈是先进后出，我们需要先访问左结点，所以先将右结点入栈），然后弹出左结点，对左结点也进行同样的操作（右结点先入栈，左结点入栈），直至栈为空并且访问完了所有结点。

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null)
        return list;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        root = stack.pop();
        list.add(root.val);
        if(root.right != null)
            stack.push(root.right);
        if(root.left != null)
            stack.push(root.left);
    }
    return list;
}

简单版非递归实现：与上一种方式的不同是在访问根节点的时机不相同。常规方式是在出栈时访问根节点，将其写入list中，而简单方式是入栈的同时将值写入list，所以我们只要保证按照前序遍历的顺序去遍历二叉树即可。

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()) {
            if(node != null) {
                stack.push(node);
                list.add(node.val);
                node = node.left;
            }else {
                node = stack.pop();
                node = node.right;
            }
        }
        return list;
    }

2）中序遍历(InOrder)：
如果二叉树为空，则什么也不做；否则：
a)中序遍历左子树；
b)访问根节点；
c)中序遍历右子树。
递归实现：

     public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        helper(root, list);
        return list;
    }
    public void helper(TreeNode root, List<Integer> list) {

        if(root.left != null)
            helper(root.left, list);
        list.add(root.val);
        if(root.right != null)
            helper(root.right, list);
    }

常规版非递归实现：从根节点依次遍历左结点，如果左结点没有被访问过，则入栈，当没有左结点或左结点被访问过的时候，弹出栈顶元素，将其写入list，并将其右结点入栈。重复上述操作。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Map<TreeNode, Integer> map = new HashMap<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) 
            return list;
        stack.push(root);
        while(!stack.isEmpty()) {
            root = stack.peek();
            while(root.left != null) {
                if(map.containsKey(root.left))
                    break;
                stack.push(root.left);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            map.put(root, 1);
            if(root.right != null)
                stack.push(root.right);
               
        }
        return list;
    }

简单版非递归实现:从根节点依次将左结点入栈，当没有左结点的时候，弹出栈顶元素，将其写入list，并将其右结点入栈。重复上述操作。与常规方法相比，省去了查看左子树是否被访问过的步骤，对每个结点，都是先遍历其左子树，所以当访问到该结点的时候，可以确保其左子树已经被访问过了，只需要访问其本身和其右结点即可。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while(node!=null || !stack.isEmpty()) {
            if(node != null) {
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                list.add(node.val);
                node = node.right;
            }
        }
        return list;
    }

3）后序遍历(PostOrder)：
如果二叉树为空，则什么也不做；否则：
a)后序遍历左子树；
b)后序遍历右子树；
c)访问根节点。
递归实现：

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        helper(root, list);
        return list;
    }
    public void helper(TreeNode root, List<Integer> list) {

        if(root.left != null)
            helper(root.left, list);

        if(root.right != null)
            helper(root.right, list);
        list.add(root.val);
    }

常规版非递归实现：将根节点左子树入栈，当访问到叶子结点，出栈，查看该叶子结点的父节点是否有右结点，有的话，如果右结点未访问则将其入栈，当一个节点的左右结点都已经访问过或者不包含左右结点，则出栈。

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Map<TreeNode, Integer> map = new HashMap<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return list;
        stack.push(root);
        while(!stack.isEmpty()) {
            root = stack.peek();
            if(root.left == null && root.right == null) {//不含左右结点时，出栈
                root = stack.pop();
                list.add(root.val);
                map.put(root, 1);
            }else if((root.left!=null && root.right == null && map.containsKey(root.left))||(root.right != null && root.left == null && map.containsKey(root.right)) || (root.left != null && root.right != null && map.containsKey(root.left) && map.containsKey(root.right))){//包含子节点，但是子节点被访问过，出栈
                root = stack.pop();
                list.add(root.val);
                map.put(root, 1);
            }else {
                while(root.left != null) {
                    if(map.containsKey(root.left)) {
                        break;
                    }
                    stack.push(root.left);
                    root = root.left;
                }
                if(root.right != null) {
                   if(map.containsKey(root.right)) {
                        break;
                    }
                    stack.push(root.right);
                }
            }
        }
        return list;
    }

简单版非递归实现：后序遍历的输出顺序是左、右、根，当我们采用先序遍历的方法，但是先遍历右子树，实现的效果是根、右、左，刚好和后序遍历的结果想法，所以我们通过add(0, node)的方式将顺序反序，达到我们想要的效果。

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()) {
            if(node != null) {
                stack.push(node);
                list.add(0, node.val);
                node = node.right;
            }else {
                node = stack.pop();
                node = node.left;
            }
        }
        return list;
    }

层次遍历：将二叉树按层输出，借助队列实现。借助null来标记一层的结束。当读取到的结点不是null，将该结点的左右结点入队列，当读到null，如果此时队列不空，则继续入null标志新的一层的结尾。

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null)
            return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(null);
        int num = 0;
        List<Integer> tempList = new ArrayList<>();
        list.add(tempList);
        while(!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            if(temp != null) {
                list.get(num).add(temp.val);
                if(temp.left != null)
                    queue.add(temp.left);
                if(temp.right != null)
                    queue.add(temp.right);
            }else {
                if(!queue.isEmpty()) {
                    num++;
                    tempList = new ArrayList<>();
                    list.add(tempList);
                    queue.add(null);
                }
            }
        }
        return list;
    }

参考：
Preorder, Inorder, and Postorder Iteratively Summarization
二叉树的几种遍历递归与非递归java实现