樹的花式遍歷需要爛熟于心。遞歸方式想必已經(jīng)信手拈來(lái)。，大部分樹類型的算法題都離不開4種遍歷。有很多基礎(chǔ)遍歷的變種，今天我們就一起理解下，樹的非遞歸的遍歷方式。

樹結(jié)構(gòu)

可愛的小樹

前序遍歷

前序遍歷 跟-左-右的順序，上述例子的遍歷結(jié)果即：[3,9,20,15,7]，非遞歸方式我們?cè)撊绾嗡伎寄兀窟@里我們可以使用棧結(jié)構(gòu)，模擬遞歸的過(guò)程。

• 輸出
• 把根放進(jìn)棧里，方便我們后續(xù)找右節(jié)點(diǎn)。
• 把左節(jié)點(diǎn)當(dāng)成根進(jìn)行下一輪循環(huán)
• 當(dāng)左節(jié)點(diǎn)為空時(shí)候，嘗試出棧上一個(gè)根節(jié)點(diǎn)
• 把右節(jié)點(diǎn)當(dāng)成根進(jìn)行下一輪循環(huán)
• 當(dāng)?？樟?當(dāng)前節(jié)點(diǎn)也空了時(shí)候 結(jié)束循環(huán)

翻譯成代碼

    public static List preOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                res.add(root.getValue());
                stack.push(root);
                root = root.getLeft();
            } else {
                root = stack.pop().getRight();
            }
        }
        return res;
    }

中序遍歷

中序遍歷 左-跟-右的順序，上述例子的遍歷結(jié)果即：[9,3,15,20,7]，這里我們依舊可以使用棧結(jié)構(gòu)，模擬遞歸的過(guò)程

• 根入棧
• 把左節(jié)點(diǎn)當(dāng)成根進(jìn)行下一輪循環(huán)
• 當(dāng)左節(jié)點(diǎn)為空時(shí)候，嘗試出棧上一個(gè)根節(jié)點(diǎn)
• 輸出
• 把右節(jié)點(diǎn)當(dāng)成根進(jìn)行下一輪循環(huán)
• 當(dāng)?？樟?當(dāng)前節(jié)點(diǎn)也空了時(shí)候 結(jié)束循環(huán)

中序跟前序差別是，中序先在節(jié)點(diǎn)出棧時(shí)進(jìn)行輸出，出棧即表示所有的左已經(jīng)入棧了

翻譯成代碼

   public static List<Integer> inOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.getLeft();
            } else {
                root = stack.pop();
                res.add(root.getValue());
                root = root.getRight();
            }
        }
        return res;
    }

后序遍歷

后序遍歷稍微麻煩一點(diǎn)， 左-右-根，這里我們依舊使用棧來(lái)實(shí)現(xiàn)

• 根先入棧
• 當(dāng)棧內(nèi)不為空時(shí)，我們進(jìn)行循環(huán)
• 我們先把當(dāng)前元素置為棧內(nèi)第一個(gè)元素
• 如果當(dāng)前元素沒(méi)左孩子也沒(méi)右孩子則輸出
• 如果當(dāng)前元素的左孩子、右孩子都輸出完了，那自己輸出
• 否則入棧右孩子，入棧左孩子
• 繼續(xù)循環(huán)

那怎么判斷左、右是不是已經(jīng)輸出完畢？
這里我們可以考慮下 一個(gè)節(jié)點(diǎn)有哪些狀態(tài)

• case1
• case2
• case3
• case4

case4 在條件如果當(dāng)前元素沒(méi)左孩子也沒(méi)右孩子則輸出種已經(jīng)輸出了，我們要考慮的只有前三個(gè)case：

• case1：當(dāng)左，右已經(jīng)遍歷則輸出根，即上一個(gè)遍歷的節(jié)點(diǎn)是右節(jié)點(diǎn)時(shí)候，輸出根
• case2: 當(dāng)右節(jié)點(diǎn)已經(jīng)遍歷則輸出根，即上一個(gè)遍歷的節(jié)點(diǎn)是右節(jié)點(diǎn)時(shí)候，輸出根
• case3: 當(dāng)左節(jié)點(diǎn)已經(jīng)遍歷則輸出根，即上一個(gè)遍歷的節(jié)點(diǎn)是左節(jié)點(diǎn)時(shí)候，輸出根

所以，我們只需要存一個(gè)前置遍歷節(jié)點(diǎn)，當(dāng)前置遍歷節(jié)點(diǎn)滿足上述case時(shí)候即可輸出根，即 當(dāng)前序是當(dāng)前節(jié)點(diǎn)的左或者右時(shí)候，即可輸出根。

翻譯成代碼：

    public static List<Integer> aftOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode cur = null, pre = new TreeNode(-1);
        while (!stack.isEmpty()) {
            cur = stack.peek();
            if ((cur.getLeft() == null && cur.getRight() == null)
                    || pre == cur.getLeft()
                    || pre == cur.getRight()) {
                res.add(cur.getValue());
                pre = stack.pop();
            } else {
                if (cur.getRight() != null)
                    stack.push(cur.getRight());
                if (cur.getLeft() != null)
                    stack.push(cur.getLeft());
            }
        }
        return res;
    }

這里需要注意個(gè)細(xì)節(jié)，pre的初始值不要設(shè)置為null,否則第一次遍歷時(shí)候，如果當(dāng)前節(jié)點(diǎn)不存在左或者右 就會(huì)存在問(wèn)題。

層序遍歷

層序遍歷相比另外三種，比較簡(jiǎn)單，我們只要用隊(duì)列實(shí)現(xiàn)即可

• 先出隊(duì)列，輸出
• 左入隊(duì)列
• 右入隊(duì)列
• 繼續(xù)循環(huán)

    public static List<Integer> floorOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            res.add(cur.getValue());
            if (cur.getLeft() != null) queue.add(cur.getLeft());
            if (cur.getRight() != null) queue.add(cur.getRight());
        }
        return res;
    }

但層序遍歷有很多變種，比如：每一層單獨(dú)一個(gè)數(shù)組，輸出每層數(shù)組的集合、Z字打印每一層等
這類我們只要在上述出棧前記錄下棧內(nèi)元素個(gè)數(shù)，即當(dāng)前層的數(shù)量，再去按數(shù)量處理即可
例子：

   public static List<List<Integer>> floorOrderWithFloor(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> data = new ArrayList<>();
            while (size-->0){
                TreeNode cur = queue.poll();
                data.add(cur.getValue());
                if (cur.getLeft() != null) queue.add(cur.getLeft());
                if (cur.getRight() != null) queue.add(cur.getRight());
            }
            res.add(data);
        }
        return res;
    }

happy ending~

源碼: 劍指offer4J