二叉树遍历迭代实现

使用迭代实现了先,中,后序遍历二叉树.时间复杂度均为O(n);

前序遍历

没什么好说的,栈中取当前节点,先压右节点,后压左节点.然后取当前节点值,取值操作任意位置即可,因为写成这样必然取当前节点是先序的.

    public static List<Object> preTraversal(BTree bTree) {
        if (bTree == null) {
            return null;
        }
        List<Object> results = new ArrayList();
        List<BTree> stack = new ArrayList();
        BTree cur = bTree;
        int len = 0;

        stack.add(cur);

        while((len = stack.size()) > 0) {
            cur = stack.remove(len - 1);
            if (cur != null) {
                stack.add(cur.right);
                stack.add(cur.left);
                results.add(cur.value);
            }
        }

        return results;
    }

中序遍历

看到了网上有这样实现中序遍历的代码,两层while循环是没有必要的.
不推荐: 时间复杂度O(n^2)

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

        Stack<TreeNode> s = new Stack<TreeNode>();

        do {
            while (root != null) {
                s.push(root);
                root = root.left;
            }
            if (!s.isEmpty()) {
                TreeNode node = s.pop();
                list.add(node.val);
                root = node.right;
            }
        } while (!s.isEmpty() || root != null);

        return list;
    }

思考中序的规则:

首先遍历左子树，然后访问根结点，最后遍历右子树

 也就是说我们有一个节点,优先会去访问其左节点,这就隐藏了一个信息(为了保证之后输出根节点,根节点需要入栈).
 同时我们要意识到,叶子节点也是根节点,不过其左右子树都为空.遍历整棵树,我们只需要输出根节点就可以做到.

什么时候可以输出根节点呢?

 当然是遍历到的当前节点为空的时候(说明要么是栈顶元素的左子树为空,要么是栈顶元素的左子树已经遍历完成).我们从栈顶取出一个根节点输出.同时,继续遍历其右子树.

推荐: 时间复杂度O(n)

    public static List<Object> inOrderTraversal(BTree bTree) {
        if (bTree == null) {
            return null;
        }
        List<Object> results = new ArrayList();
        List<BTree> stack = new ArrayList();
        BTree cur = bTree;
        int len = 0;

        while(cur != null || (len = stack.size()) > 0) {
            if (cur != null) {
                stack.add(cur);
                cur = cur.left;
            } else {
                cur = stack.remove(len - 1);
                results.add(cur.value);
                cur = cur.right;
            }
        }

        return results;
    }

后序遍历

思考后序遍历的规则

首先遍历左子树，然后遍历右子树，最后访问根结点。

我们可以通过标记上一次访问的节点,来判断是否访问过该节点的左右子树

    public static List<Object> postOrderTraversal(BTree bTree) {
        if (bTree == null) {
            return null;
        }
        List<Object> results = new ArrayList<>();
        List<BTree> stack = new ArrayList<>();
        int len = 0;
        BTree cur = bTree;
        BTree last = null;
        stack.add(cur);

        while((len = stack.size()) > 0) {
            cur = stack.get(len - 1);
            boolean isLeaf = cur.left == null && cur.right == null;
            boolean isVisited = (cur.right == null && cur.left == last) || cur.right == last;

            if (isLeaf || isVisited) {
                stack.remove(len - 1);
                results.add(cur.value);
                last = cur;
            } else {
                if (cur.right != null) {
                    stack.add(cur.right);
                }
                if (cur.left != null) {
                    stack.add(cur.left);
                }
            }
        }

        return results;
    }

层次遍历

这个也没啥好说的,通过队列先进先出的特性进行广度遍历, 注意先出队

    public static List<Object> levelTraversal(BTree bTree) {
        if (bTree == null) {
            return null;
        }
        List<BTree> queue = new LinkedList<>();
        List<Object> results = new ArrayList<>();
        BTree cur = bTree;
        int len = 0;
        queue.add(cur);

        while((len = queue.size()) > 0) {
            cur = queue.remove(0);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
            results.add(cur.value);
        }

        return results;
    }