算法练习(11)-二叉树的各种遍历

public class TreeNode {

    public TreeNode left;
    public TreeNode right;
    public int val;

    public TreeNode(int val) {
        this.val = val;
    }

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

public static void foo(TreeNode n1) {
    if (n1 == null) {
        return;
    }

    System.out.printf("(1):" + n1.val + "  ");

    foo(n1.left);
    System.out.printf("(2):" + n1.val + "  ");

    foo(n1.right);
    System.out.printf("(3):" + n1.val + "  ");

}

/**
 * 前序遍历(非递归版): root-left-right
 *
 * @param root
 */
static void preOrderUnRecur(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        System.out.print(n.val + " ");
        if (n.right != null) {
            stack.add(n.right);
        }
        if (n.left != null) {
            stack.add(n.left);
        }
    }
}

/**
 * 中序遍历(非递归版): left-root-right
 * 思路: 不停压入左边界(即:头-左),直到null,
 *       然后弹出打印过程中,发现有右孩子,则压栈
 *       然后再对右孩子,不停压入左边界
 * @param n
 */
static void inOrderUnRecur(TreeNode n) {
    Stack<TreeNode> stack = new Stack<>();
    while (n != null || !stack.isEmpty()) {
        if (n != null) {
            //左边界进栈,直到最末端
            stack.push(n);
            n = n.left;
        } else {
            //跳到右边,压入右节点(压完后,n不为空,会重新进入上面的左边界处理)
            n = stack.pop();
            System.out.print(n.val + " ");
            n = n.right;
        }
    }
}

/**
 * 后序遍历(非递归版): left-right-root
 *
 * @param root
 */
static void postOrderUnRecur(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    //用于收集最后所有"排好序"的节点
    Stack<TreeNode> result = new Stack<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        result.add(n);
        if (n.left != null) {
            stack.add(n.left);
        }
        if (n.right != null) {
            stack.add(n.right);
        }
    }
    while (!result.isEmpty()) {
        System.out.print(result.pop().val + " ");
    }
}

public static void levelOrder(TreeNode n1) {
    if (n1 == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(n1);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.printf(node.val + " ");
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

static void levelOrder2(TreeNode n) {
    if (n == null) {
        return;
    }
    int currLevel = 1;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(n);

    //弄1个map,记录每个元素所在的层
    Map<TreeNode, Integer> levelMap = new HashMap<>();
    levelMap.put(n, 1);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        //从map取查找出队元素所在的层
        int nodeLevel = levelMap.get(node);
        //如果与当前层不一样,说明来到了下一层(关键!)
        if (currLevel != nodeLevel) {
            currLevel += 1;
            //输出换行符
            System.out.println();
        }
        System.out.print(node.val + " ");
        if (node.left != null) {
            //左节点入队,说明取到了下层,把下层元素提前放入map
            levelMap.put(node.left, currLevel + 1);
            queue.add(node.left);
        }
        if (node.right != null) {
            //右节点入队,说明取到了下层,把下层元素提前放入map
            levelMap.put(node.right, currLevel + 1);
            queue.add(node.right);
        }
    }
}

    static void levelOrder3(TreeNode n) {
        if (n == null) {
            return;
        }
        //curEnd:本层最后1个节点
        //nextEnd:下层最后1个节点
        TreeNode curEnd = n, nextEnd = null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(n);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.printf(node.val + " ");
            //逐层入队
            //注:queue中,最多只会有头-左-右 3个节点
            //入队过程中,nextEnd最终肯定会指向本层最后1个节点
            if (node.left != null) {
                queue.add(node.left);
                nextEnd = node.left;
            }
            if (node.right != null) {
                queue.add(node.right);
                nextEnd = node.right;
            }
            if (node == curEnd) {
                //如果出队的元素, 已经是本层最后1个,说明这层到头了
                System.out.printf("\n");
                //进入下一层后,重新标识curEnd
                curEnd = nextEnd;
            }
        }
    }