這里就對(duì)二叉樹(shù)的遍歷方式進(jìn)行總結(jié)

abstract.jpeg

基于遞歸的遍歷

前序遍歷

前序遍歷：即對(duì)二叉樹(shù)按照當(dāng)前節(jié)點(diǎn)、左子樹(shù)、右子樹(shù)的順序進(jìn)行遍歷。顯然借助遞歸，非常容易實(shí)現(xiàn)、理解

/**
 * 基于遞歸的前序遍歷
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        dfs(root, list);
        return list;
    }

    private void dfs(TreeNode cur, List<Integer> list) {
        if( cur==null ) {
            return;
        }

        // 1. 處理當(dāng)前節(jié)點(diǎn)
        list.add( cur.val );

        // 2. 處理左子樹(shù)
        dfs(cur.left, list);

        // 3. 處理右子樹(shù)
        dfs(cur.right, list);
    }
}

中序遍歷

中序遍歷：即對(duì)二叉樹(shù)按照左子樹(shù)、當(dāng)前節(jié)點(diǎn)、右子樹(shù)的順序進(jìn)行遍歷。顯然借助遞歸，非常容易實(shí)現(xiàn)、理解

/**
 * 基于遞歸的中序遍歷
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        dfs(root, list);
        return list;
    }

    private void dfs(TreeNode cur, List<Integer> list) {
        if( cur==null ) {
            return;
        }

        // 1. 處理左子樹(shù)
        dfs(cur.left, list);

        // 2. 處理當(dāng)前節(jié)點(diǎn)
        list.add( cur.val );

        // 3. 處理右子樹(shù)
        dfs(cur.right, list);
    }
}

后序遍歷

后序遍歷：即對(duì)二叉樹(shù)按照左子樹(shù)、右子樹(shù)、當(dāng)前節(jié)點(diǎn)的順序進(jìn)行遍歷。顯然借助遞歸，非常容易實(shí)現(xiàn)、理解

/**
 * 基于遞歸的后序遍歷
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        dfs(root, list);
        return list;
    }

    private void dfs(TreeNode cur, List<Integer> list) {
        if( cur==null ) {
            return;
        }

        // 1. 處理左子樹(shù)
        dfs(cur.left, list);

        // 2. 處理右子樹(shù)
        dfs(cur.right, list);

        // 3. 處理當(dāng)前節(jié)點(diǎn)
        list.add( cur.val );
    }
}

基于迭代的遍歷

前序遍歷

不同于遞歸隱式維護(hù)棧的便捷，在通過(guò)迭代進(jìn)行遍歷時(shí)需要我們顯式地維護(hù)一個(gè)棧。具體地，在前序遍歷當(dāng)中。首先需要處理對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理、然后沿著左子樹(shù)一直入棧。當(dāng)左子樹(shù)遍歷完畢, 通過(guò)出棧獲取父節(jié)點(diǎn)來(lái)對(duì)右子樹(shù)再進(jìn)行處理

/**
 * 基于迭代的前序遍歷
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();

        while ( root!=null || !stack.isEmpty() ) {
            while (root!=null) {
                // 先處理當(dāng)前節(jié)點(diǎn)
                res.add( root.val );
                // 然后沿左子樹(shù)一直入棧
                stack.addLast( root );
                root = root.left;
            }

            // 左子樹(shù)遍歷完畢, 通過(guò)父節(jié)點(diǎn)來(lái)對(duì)右子樹(shù)再進(jìn)行處理
            TreeNode parent = stack.removeLast();
            root = parent.right;
        }

        return res;
    }
}

中序遍歷

不同于遞歸隱式維護(hù)棧的便捷，在通過(guò)迭代進(jìn)行遍歷時(shí)需要我們顯式地維護(hù)一個(gè)棧。具體地，在中序遍歷當(dāng)中。首先沿著左子樹(shù)一直入棧。當(dāng)左子樹(shù)遍歷完畢, 通過(guò)出棧獲取父節(jié)點(diǎn)并對(duì)其進(jìn)行處理，最后對(duì)右子樹(shù)再進(jìn)行處理


/**
 * 基于迭代的中序遍歷
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();

        while ( root!=null || !stack.isEmpty() ) {
            while ( root!=null ) {
                // 先沿左子樹(shù)一直入棧
                stack.addLast( root );
                root = root.left;
            }

            // 左子樹(shù)遍歷完畢, 獲取父節(jié)點(diǎn)
            TreeNode parent = stack.removeLast();
            // 處理父節(jié)點(diǎn)的值
            res.add( parent.val );
            // 通過(guò)父節(jié)點(diǎn)對(duì)右子樹(shù)再進(jìn)行處理
            root = parent.right;
        }

        return res;
    }
}

后序遍歷

后序遍歷的順序是左、右、當(dāng)前。如果直接使用棧按這個(gè)順序進(jìn)行遍歷輸出會(huì)比較麻煩。故我們可以先按照當(dāng)前、右、左的順序進(jìn)行迭代遍歷，顯然這個(gè)過(guò)程與前序遍歷非常類(lèi)似，只是需要把代碼中涉及左、右子樹(shù)的調(diào)換下即可。最后對(duì)遍歷結(jié)果進(jìn)行翻轉(zhuǎn)。這樣遍歷結(jié)果就由當(dāng)前、右、左就變?yōu)?左、右、當(dāng)前。即我們所需的后序遍歷結(jié)果

/**
 * 基于迭代的后序遍歷
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();

        // 先按 根、右、左 的順序進(jìn)行遍歷
        while ( root!=null || !stack.isEmpty() ) {
            while (root!=null) {
                // 先處理當(dāng)前節(jié)點(diǎn)
                res.add( root.val );
                // 然后沿右子樹(shù)一直入棧
                stack.addLast( root );
                root = root.right;
            }

            // 右子樹(shù)遍歷完畢, 通過(guò)父節(jié)點(diǎn)獲取左子樹(shù)再進(jìn)行處理
            TreeNode parent = stack.removeLast();
            root = parent.left;
        }

        // 對(duì)遍歷結(jié)果進(jìn)行翻轉(zhuǎn)
        // 這樣遍歷結(jié)果就由 根、右、左 就變?yōu)?nbsp;左、右、根, 即后序遍歷
        Collections.reverse( res );
        return res;
    }
}

層序遍歷

對(duì)于二叉樹(shù)的層序遍歷就簡(jiǎn)單很多了。我們借助隊(duì)列的FIFO特性即可輕松實(shí)現(xiàn)

class Solution {
    public List<Integer> levelOrder(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }

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

        while ( !queue.isEmpty() ) {
            // 彈出隊(duì)首元素, 進(jìn)行處理
            TreeNode cur = queue.poll();
            res.add( node.val );

            // 將當(dāng)前節(jié)點(diǎn)的左、右子節(jié)點(diǎn)加入隊(duì)列
            if( node.left != null ) {
                queue.add( node.left );    
            }           
            if( node.right != null ) {
                queue.add( node.right );    
            }
        }

        return res;
    }
}

基于Morris算法的遍歷

基本原理

Morris算法為二叉樹(shù)的遍歷提供了新的思路，其通過(guò)充分利用樹(shù)中葉子節(jié)點(diǎn)存在大量空指針這一特點(diǎn)。實(shí)現(xiàn)了常數(shù)級(jí)別的空間復(fù)雜度。在進(jìn)一步介紹該算法之前，我們先來(lái)說(shuō)明一個(gè)概念——mostRight節(jié)點(diǎn)。其用于表示當(dāng)前節(jié)點(diǎn)cur的左子樹(shù)的最右節(jié)點(diǎn)。例如下圖的一個(gè)二叉樹(shù)。如果當(dāng)前節(jié)點(diǎn)為1，則mostRight節(jié)點(diǎn)即為5；如果當(dāng)前節(jié)點(diǎn)為3，則mostRight節(jié)點(diǎn)即為6

figure 1.jpeg

實(shí)際上，Morris算法非常簡(jiǎn)單。其基本遍歷流程如下：

將當(dāng)前節(jié)點(diǎn)cur初始化為root
當(dāng)前節(jié)點(diǎn)cur如果不存在左子樹(shù)。則將當(dāng)前節(jié)點(diǎn)指向其右子樹(shù)，以便遍歷當(dāng)前節(jié)點(diǎn)的右子樹(shù)
當(dāng)前節(jié)點(diǎn)cur如果存在左子樹(shù)，則先獲取cur節(jié)點(diǎn)的mostRight節(jié)點(diǎn)

如果mostRight節(jié)點(diǎn)的右子節(jié)點(diǎn)為空，此時(shí)說(shuō)明cur節(jié)點(diǎn)的左子樹(shù)還未遍歷。故：一方面，我們將mostRight節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)置為cur節(jié)點(diǎn)；另一方面，將當(dāng)前節(jié)點(diǎn)指向其左子樹(shù)，以便遍歷當(dāng)前節(jié)點(diǎn)的左子樹(shù)
如果mostRight節(jié)點(diǎn)的右子節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)cur，此時(shí)說(shuō)明cur節(jié)點(diǎn)的左子樹(shù)已經(jīng)遍歷完成。故：一方面，我們將mostRight節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)置為null空指針；另一方面，將當(dāng)前節(jié)點(diǎn)指向其右子樹(shù)，以便遍歷當(dāng)前節(jié)點(diǎn)的右子樹(shù)

重復(fù)Step 2、Step 3，直到當(dāng)前節(jié)點(diǎn)cur為null時(shí)為止

該算法遍歷過(guò)程的示意圖如下，可以看到當(dāng)一個(gè)節(jié)點(diǎn)的左子樹(shù)未遍歷完時(shí)，Morris算法會(huì)利用原葉子節(jié)點(diǎn)的null空指針修改樹(shù)。而當(dāng)該節(jié)點(diǎn)的左子樹(shù)遍歷后，會(huì)把對(duì)樹(shù)的修改進(jìn)行撤回。以恢復(fù)樹(shù)原有的結(jié)構(gòu)

figure 2.jpeg

前序遍歷

這里基于Morris算法來(lái)實(shí)現(xiàn)前序遍歷。問(wèn)題的關(guān)鍵就在于何時(shí)對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理。顯然這里有兩個(gè)時(shí)機(jī)，一方面，遍歷過(guò)程中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)為空。則在對(duì)當(dāng)前節(jié)點(diǎn)的右子樹(shù)進(jìn)行遍歷前，需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理；另一方面，遍歷過(guò)程中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)不為空，則在對(duì)當(dāng)前節(jié)點(diǎn)的左子樹(shù)進(jìn)行遍歷前，需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理

/**
 * 基于Morris算法的前序遍歷
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if( root == null ) {
            return res;
        }

        TreeNode cur = root;
        // 當(dāng)前節(jié)點(diǎn)cur的左子樹(shù)的最右節(jié)點(diǎn)
        TreeNode mostRight = null;

        while ( cur != null ) {
            // 當(dāng)前節(jié)點(diǎn)的左子樹(shù)為空
            if( cur.left == null ) {
                // 處理當(dāng)前節(jié)點(diǎn)
                res.add( cur.val );
                // 處理當(dāng)前節(jié)點(diǎn)的右子樹(shù)
                cur = cur.right;
            } else {    // 當(dāng)前節(jié)點(diǎn)的左子樹(shù)不為空
                // 尋找當(dāng)前節(jié)點(diǎn)cur的左子樹(shù)的最右節(jié)點(diǎn)
                mostRight = cur.left;
                while ( mostRight.right!=null && mostRight.right!=cur ) {
                    mostRight = mostRight.right;
                }

                if( mostRight.right == null) {  // 說(shuō)明cur節(jié)點(diǎn)的左子樹(shù)未遍歷
                    // 處理當(dāng)前節(jié)點(diǎn)
                    res.add( cur.val );
                    // 處理當(dāng)前節(jié)點(diǎn)的左子樹(shù)
                    mostRight.right = cur;
                    cur = cur.left;
                } else if ( mostRight.right == cur ) {  // 說(shuō)明cur節(jié)點(diǎn)的左子樹(shù)已經(jīng)遍歷完成
                    // 處理當(dāng)前節(jié)點(diǎn)的右子樹(shù)
                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }

        return res;
    }
}

中序遍歷

這里基于Morris算法來(lái)實(shí)現(xiàn)中序遍歷。問(wèn)題的關(guān)鍵就在于何時(shí)對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理。顯然這里有兩個(gè)時(shí)機(jī)，一方面，遍歷過(guò)程中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)為空。則在對(duì)當(dāng)前節(jié)點(diǎn)的右子樹(shù)進(jìn)行遍歷前，需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理；另一方面，遍歷過(guò)程中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)不為空，則在對(duì)當(dāng)前節(jié)點(diǎn)的左子樹(shù)完成遍歷后，需要對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理

/**
 * 基于Morris算法的中序遍歷
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if( root == null ) {
            return res;
        }

        TreeNode cur = root;
        // 當(dāng)前節(jié)點(diǎn)cur的左子樹(shù)的最右節(jié)點(diǎn)
        TreeNode mostRight = null;

        while ( cur != null ) {
            // 當(dāng)前節(jié)點(diǎn)的左子樹(shù)為空
            if( cur.left == null ) {
                // 處理當(dāng)前節(jié)點(diǎn)
                res.add( cur.val );
                // 處理當(dāng)前節(jié)點(diǎn)的右子樹(shù)
                cur = cur.right;
            } else {    // 當(dāng)前節(jié)點(diǎn)的左子樹(shù)不為空
                // 尋找當(dāng)前節(jié)點(diǎn)cur的左子樹(shù)的最右節(jié)點(diǎn)
                mostRight = cur.left;
                while ( mostRight.right!=null && mostRight.right!=cur ) {
                    mostRight = mostRight.right;
                }

                if( mostRight.right == null) {  // 說(shuō)明cur節(jié)點(diǎn)的左子樹(shù)未遍歷
                    // 處理當(dāng)前節(jié)點(diǎn)的左子樹(shù)
                    mostRight.right = cur;
                    cur = cur.left;
                } else if ( mostRight.right == cur ) {  // 說(shuō)明cur節(jié)點(diǎn)的左子樹(shù)已經(jīng)遍歷完成
                    // 處理當(dāng)前節(jié)點(diǎn)
                    res.add( cur.val );
                    // 處理當(dāng)前節(jié)點(diǎn)的右子樹(shù)
                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }

        return res;
    }
}

Note

這里給出本文中關(guān)于樹(shù)節(jié)點(diǎn)的類(lèi)定義

/**
 * 樹(shù)的節(jié)點(diǎn)
 */
class TreeNode {
    TreeNode left;
    
    TreeNode right;
    
    int val;
    
    TreeNode() {
    }
    
    TreeNode(int val) {
        this.val = val; 
    }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

淺談二叉樹(shù)遍歷

基于遞歸的遍歷

前序遍歷

中序遍歷

后序遍歷

基于迭代的遍歷

前序遍歷

中序遍歷

后序遍歷

層序遍歷

基于Morris算法的遍歷

基本原理

前序遍歷

中序遍歷

Note