树

二叉树的遍历

前序遍历

    public void before_dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        System.out.println(node.val);
        before_dfs(node.left);
        before_dfs(node.right);
    }

// 非递归的方式。
    public void before(TreeNode node) {
        if (node == null) {
            return;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        while (node != null || !queue.isEmpty()) {
            while (node != null) {
                System.out.println(node.val);
                queue.addFirst(node);
                node = node.left;
            }

            if (!queue.isEmpty()) {
                node = queue.removeFirst();
                node = node.right;
            }
        }
    }

中序遍历

    public void mid_dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        before_dfs(node.left);
        System.out.println(node.val);
        before_dfs(node.right);
    }

// 非递归版中序遍历。不断入队左子树，直到左子树为空，出队一个，设置当前节点为出队节点的右子树，然后继续从头循环。
    public void mid(TreeNode node) {
        if (node == null) {
            return;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        while (node != null || !queue.isEmpty()) {
            while (node != null) {
                queue.addFirst(node);
                node = node.left;
            }

            if (!queue.isEmpty()) {
                node = queue.removeFirst();
                System.out.println(node.val);
                node = node.right;
            }
        }
    }

后序遍历

    public void after_dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        before_dfs(node.left);
        before_dfs(node.right);
        System.out.println(node.val);
    }

// 不断遍历左子树，遇到左子树为空，peek出栈第一个节点，判断新节点右子树是否为空，不为空则继续从左子树开始遍历；如果新节点右子树之前遍历过，则remove此节点，设置上一个遍历过得节点为此节点。
    public void after(TreeNode node) {
        if (node == null) {
            return;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        while (node != null || !queue.isEmpty()) {
            while (node != null) {
                queue.addFirst(node);
                node = node.left;
            }

            boolean tag = true;
            TreeNode preNode = null;  // 前驱节点
            while (!queue.isEmpty() && tag) {
                node = queue.getFirst();
                if (node.right == preNode) { // 之前访问的为空节点或是栈顶节点的右子节点
                    node = queue.removeFirst();
                    System.out.println(node.val);
                    if (queue.isEmpty()) {
                        return;
                    } else {
                        preNode = node;
                    }
                } else {
                    node = node.right;
                    tag = false;
                }
            }
        }
    }

层次遍历

层次遍历与前中后序遍历不同，层次遍历需要使用队列，而不是栈！

public List<List<Integer>> level(TreeNode node) {
    List<List<Integer>> rst = new ArrayList<>();
    if (node == null) {
        return rst;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    queue.addLast(node);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> levelList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.removeFirst();
            levelList.add(cur.val);
            if (cur.left != null) {
                queue.addLast(cur.left);
            }
            if (cur.right != null) {
                queue.addLast(cur.right);
            }
        }
        rst.add(levelList);
    }

    return rst;
}

锯齿形层序遍历

思路和层序遍历一致，但是要维护个标志，标识下一层的遍历方向！

这里有个小技巧，与其说是锯齿形遍历，不如说在每一层从左往右遍历时，将当前节点值添加到双端队列的头还是尾！

这是一道不该失败的题！

public List<List<Integer>> zigZagLevel(TreeNode node) {
    List<List<Integer>> rst = new ArrayList<>();
    if (node == null) {
        return rst;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    queue.addLast(node);
    boolean isLeft = true;
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> levelList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.removeFirst();
            if (isLeft) {
                levelList.addLast(cur.val);
            } else {
                levelList.addFirst(cur.val);
            }
            if (cur.left != null) {
                queue.addLast(cur.left);
            }
            if (cur.right != null) {
                queue.addLast(cur.right);
            }
        }
        isLeft = !isLeft;
        rst.add(levelList);
    }

    return rst;
}