鏡像二叉樹的示例分析，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

創(chuàng)新互聯(lián)是專業(yè)的沁源網(wǎng)站建設公司，沁源接單;提供成都做網(wǎng)站、網(wǎng)站建設,網(wǎng)頁設計,網(wǎng)站設計,建網(wǎng)站,PHP網(wǎng)站建設等專業(yè)做網(wǎng)站服務;采用PHP框架,可快速的進行沁源網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!

算法這個東西很難，縱使你了解了其中的邏輯，用代碼寫出來仍然不是一件容易的事，內(nèi)部有太多的細節(jié)需要處理。為了便于大伙輕松理解算法邏輯，對于所有的題目，我會使用圖文加動畫的形式進行講解，讓讀者可以輕松理解算法邏輯的同時，還可以留下深刻的影像不容易遺忘。

好，下面我們開始今天的算法題：鏡像二叉樹，就是將一顆二叉樹上的左右節(jié)點全部交換，就好比鏡子里的二叉樹，左右方向是反過來的。

二叉樹節(jié)點表示

class Node {
    T value;
    Node left;
    Node right;

    Node(T value) {
        this.value = value;
    }

    Node(T value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

一個參數(shù)的構造器是葉子節(jié)點，三個參數(shù)的構造器是中間節(jié)點，看到這里讀者應該知道這是 Java 語言，我使用了范型 

構造二叉樹

Node node2 = new Node<>(2);
Node node3 = new Node<>(3);
Node node1 = new Node<>(1, node2, node3);

// 一次性構造
Node node1 = new Node<>(1, new Node<>(2), new Node<>(3));

呈現(xiàn)二叉樹結構

如果我們正確寫出了鏡像算法，那如何來直觀驗證鏡像的結構是否正確呢？LeetCode 使用的是單元測試，它使用一系列的單元測試和壓力測試腳本代碼來驗證用戶編寫的算法的正確性和性能。但是我們不要這樣做，因為不直觀。我們選擇對二叉樹的結構內(nèi)容進行直觀的呈現(xiàn)，如此就可以使用肉眼來進行快速驗證。如何直觀呈現(xiàn)呢？我們使用最簡單的括號表示法，它并不是最直觀的，但是它易于實現(xiàn)。

class Node {
  T value;
  Node left;
  Node right;

  public String toString() {
    // 葉節(jié)點
    if (left == right) {
        return String.format("[%d]", value);
    }
    // 中間節(jié)點
    return String.format("(%d, %s, %s)", value, left, right);
  }
}

Node node2 = new Node<>(2);
Node node3 = new Node<>(3);
Node node1 = new Node<>(1, node2, node3);

System.out.println(node1);
System.out.println(node2);
System.out.println(node3);
---------------------
[2]
[3]
(1, [2], [3])

遞歸鏡像二叉樹

鏡像二叉樹有兩種算法，一種是遞歸，一種是迭代。遞歸的算法簡單易于理解，我們先使用遞歸算法來求解。遞歸的思想就是深度遍歷，遇到一個節(jié)點，先遞歸鏡像它的左子樹，再遞歸鏡像它的右子樹，然后再交換自己的左右子樹。如果遇到的是葉子節(jié)點，就不必處理了。為了避免無限遞歸，一定要及時設置好遞歸的停止條件，在這里停止條件就是遇到了葉節(jié)點。

public void mirrorFrom(Node node) {
    // 葉子結點
    if (node.left == node.right) {
        return;
    }
    // 遞歸鏡像左子樹
    if (node.left != null)
        mirrorFrom(node.left);
    // 遞歸鏡像右子樹
    if (node.right != null)
        mirrorFrom(node.right);
    // 交換當前節(jié)點的左右子樹
    Node tmp = node.left;
    node.left = node.right;
    node.right = tmp;
}

迭代鏡像二叉樹

遞歸算法的優(yōu)勢在于邏輯簡單，缺點在于每一次遞歸調(diào)用函數(shù)都會增加一個新的函數(shù)堆棧，如果樹的深度太深，函數(shù)的堆棧內(nèi)存就會持續(xù)走高，一不小心就會觸發(fā)臭名昭著的異常 StackOverflowException。如果二叉樹分布比較均勻，那么樹就不會太深，但是遇到偏向的二叉樹，比如所有的子節(jié)點都掛在了右節(jié)點上，二叉樹就退化成了線性鏈表，鏈表的長度就是樹的深度，那這顆樹的深度就比較可怕了。

所以下面我來介紹第二種算法 —— 迭代算法。迭代的基本思想就是將遞歸算法轉換成循環(huán)算法，用一個 for 循環(huán)來交換所有節(jié)點的左右子樹。我們需要再重新理解一下算法的目標，這個目標非常簡單，就是遍歷整顆二叉樹，將遍歷途中遇到的所有中間節(jié)點的左右指針交換一下。

那如何設計這個循環(huán)呢？一個很明顯的方法是分層循環(huán)，第一次循環(huán)處理第 1 層二叉樹節(jié)點，也就是唯一的根節(jié)點。下一個循環(huán)處理第 2 層二叉樹節(jié)點，也就是根節(jié)點的兩個兒子。如此一直處理到最底層，循環(huán)的終止條件就是后代節(jié)點沒有了。所以我們需要使用一個容器來容納下一次循環(huán)需要處理的后代節(jié)點。

public MirrorBinaryTree mirrorByLoop() {
    // 空樹不必處理
    if (root == null) {
        return this;
    }
    // 當前循環(huán)需要處理的節(jié)點
    LinkedList> expandings = new LinkedList<>();
    expandings.add(root);
    // 沒有后臺節(jié)點就可以終止循環(huán)
    while (!expandings.isEmpty()) {
        // 下一次循環(huán)需要處理的節(jié)點
        // 也就是當前節(jié)點的所有兒子節(jié)點
        LinkedList> nextExpandings = new LinkedList<>();
        // 遍歷處理當前層的所有節(jié)點
        for (Node node : expandings) {
            // 將后代節(jié)點收集起來，留著下一次循環(huán)
            if (node.left != null) {
                nextExpandings.add(node.left);
            }
            if (node.right != null) {
                nextExpandings.add(node.right);
            }
            // 交換當前節(jié)點的左右指針
            Node tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        // 將后代節(jié)點設置為下一輪循環(huán)的目標節(jié)點
        expandings = nextExpandings;
    }
    return this;
}

完整代碼

下面的完整代碼可以拷貝過去直接運行，如果讀者還是不夠明白歡迎在留言區(qū)及時提問。

package leetcode;

import java.util.LinkedList;

public class MirrorBinaryTree {

    static class Node {
        T value;
        Node left;
        Node right;

        Node(T value) {
            this.value = value;
        }

        Node(T value, Node left, Node right) {
            this(value);
            this.left = left;
            this.right = right;
        }

        public String toString() {
            if (left == right) {
                return String.format("[%d]", value);
            }
            return String.format("(%d, %s, %s)", value, left, right);
        }

    }

    private Node root;

    public MirrorBinaryTree(Node root) {
        this.root = root;
    }

    public MirrorBinaryTree mirrorByLoop() {
        if (root == null) {
            return this;
        }
        LinkedList> expandings = new LinkedList<>();
        expandings.add(root);
        while (!expandings.isEmpty()) {
            LinkedList> nextExpandings = new LinkedList<>();
            for (Node node : expandings) {
                if (node.left != null) {
                    nextExpandings.add(node.left);
                }
                if (node.right != null) {
                    nextExpandings.add(node.right);
                }
                Node tmp = node.left;
                node.left = node.right;
                node.right = tmp;
            }
            expandings = nextExpandings;
        }
        return this;
    }

    public MirrorBinaryTree mirrorByRecursive() {
        mirrorFrom(root);
        return this;
    }

    public void mirrorFrom(Node node) {
        if (node.left == node.right) {
            return;
        }

        if (node.left != null)
            mirrorFrom(node.left);
        if (node.right != null)
            mirrorFrom(node.right);

        Node tmp = node.left;
        node.left = node.right;
        node.right = tmp;
    }

    public String toString() {
        if (root == null) {
            return "()";
        }
        return root.toString();
    }

    public static void main(String[] args) {
        Node root = new Node<>(
                1, 
                new Node<>(
                        2, 
                        new Node<>(4), 
                        new Node<>(
                                5, 
                                new Node<>(8),
                                null)),
                new Node<>(
                        3, 
                        new Node<>(
                                6, 
                                null, 
                                new Node<>(9)), 
                        new Node<>(7)));
        MirrorBinaryTree tree = new MirrorBinaryTree<>(root);
        System.out.println(tree);
        tree.mirrorByRecursive();
        System.out.println(tree);
        tree.mirrorByLoop();
        System.out.println(tree);
    }

}
---------------
(1, (2, [4], (5, [8], null)), (3, (6, null, [9]), [7]))
(1, (3, [7], (6, [9], null)), (2, (5, null, [8]), [4]))
(1, (2, [4], (5, [8], null)), (3, (6, null, [9]), [7]))

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注創(chuàng)新互聯(lián)-成都網(wǎng)站建設公司行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。

網(wǎng)頁題目：鏡像二叉樹的示例分析-創(chuàng)新互聯(lián)
標題鏈接：http://www.xueling.net.cn/article/doosho.html