二叉树的遍历

  

引言：

对于二叉树的递归遍历比较简单，所以本文主要想讨论的是非递归版。其中，中序遍历和前序遍历的非递归写法都比较简单，后序遍历最难。

一、二叉树节点表示

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

二、前序遍历

2.1 递归版本

public static void preOrder1(TreeNode root){
    if(root == null)
        return;
    System.out.println(root.val);
    preOrder1(root.left);
    preOrder1(root.right);
}

2.2 非递归版本

public static void preOrder2(TreeNode root){
    Stack<TreeNode>  stack = new Stack<>();
    TreeNode node = root;
    while(node != null || !stack.empty()){
        if(node != null){
            System.out.println(node.val);
            stack.push(node);
            node = node.left;
        }else{
            node = stack.pop();
            node = node.right;
        }
    }
}

三、中序遍历

3.1 递归版本

public static void inOrder1(TreeNode root){
    if(root == null)
        return;
    inOrder1(root.left);
    System.out.println(root.val);
    inOrder1(root.right);
}

3.2 非递归版本

public static void inOrder2(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode node= root;
    while(node != null || !stack.empty()){
        if(node != null){
            stack.push(node);
            node = node.left;
        }else {
            node = stack.pop();
            System.out.println(node.val);
            node = node.right;
        }
    }
}

四、后序遍历

4.1 递归版本

public static void postOrder1(TreeNode root){
    if(root == null)
        return;
    postOrder1(root.left);
    postOrder1(root.right);
    System.out.println(root.val);
}

4.2 非递归版本

public static void postOrder2(TreeNode root){
    Stack<TreeNode> stack  = new Stack<TreeNode>();
    TreeNode node = root;
    TreeNode lastNode = root;//主要用来记录上次访问的节点。判断上次访问的节点是否为当前节点的右节点
    while(node != null || !stack.empty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.peek();
		//①当前节点没有右节点；②当前节点的右节点已访问过
        if (node.right == null || node.right == lastNode) {
            System.out.println(node.val);
            stack.pop();
            lastNode = node;
            node = null;
        } else {
            node = node.right;
        }
    }
}

五、层序遍历

public static void LevelorderTraversal ( TreeNode root )
{
     LinkedList<TreeNode> Q = new LinkedList<TreeNode>();
     TreeNode node = root;

     if (node == null) return; /* 若是空树则直接返回 */
     Q.offer(node);
     while (!Q.isEmpty()) {
         node = Q.poll();
         System.out.println(node.val); /* 访问取出队列的结点 */
         if (node.left != null) Q.offer(node.left);
         if (node.right != null) Q.offer(node.right);
     }
}