二叉树非递归遍历--前中后序

本文主要是介绍二叉树非递归遍历--前中后序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

代码

public class BTreeTraverseMethods {

    static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

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

    public static void preOrderTraverse(TreeNode root) {
        System.out.print("Pre-Order Traverse:");
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        System.out.println();
    }

    public static void inOrderTraverse(TreeNode root) {
        System.out.print("In-Order Traverse:");
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode popElem = stack.pop();
                System.out.print(popElem.val + " ");
                if (popElem.right != null) {
                    node = popElem.right;
                }
            }
        }
        System.out.println();
    }

    public static void postOrderTraverse(TreeNode root) {
        System.out.print("Post-Order Traverse:");
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode pre = null, node;
        while (!stack.isEmpty()) {
            node = stack.peek();
            // 出栈条件: 叶子结点 || (前序节点不为空 && (该节点没有右子树并且前序节点是左节点 || 该节点的右节点是前序节点))
            if ((node.left == null && node.right == null) || (pre != null &&
                    (node.right == null && node.left == pre || node.right == pre))) {
                TreeNode popElem = stack.pop();
                System.out.print(popElem.val + " ");
                pre = node;
            } else {
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(5);
        head.left = new TreeNode(2);
        head.right = new TreeNode(6);
        head.left.left = new TreeNode(1);
        head.left.right = new TreeNode(3);
        head.right.right = new TreeNode(8);

        preOrderTraverse(head);
        inOrderTraverse(head);
        postOrderTraverse(head);
    }
}

结果

Pre-Order Traverse:5 2 1 3 6 8 
In-Order Traverse:1 2 3 5 6 8 
Post-Order Traverse:1 3 2 8 6 5 

总结

• 二叉树遍历的思路很容易理解不做过多阐述.
• 二叉树的遍历以及它衍生的题目是面试中比较常见的手撕代码题, 例如判断是否为二叉排序树可以用中序是否有序来判断等.

这篇关于二叉树非递归遍历--前中后序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！