溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
鏡像二叉樹的示例分析，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
算法這個東西很難，縱使你了解了其中的邏輯，用代碼寫出來仍然不是一件容易的事，內部有太多的細節(jié)需要處理。為了便于大伙輕松理解算法邏輯，對于所有的題目，我會使用圖文加動畫的形式進行講解，讓讀者可以輕松理解算法邏輯的同時，還可以留下深刻的影像不容易遺忘。
好，下面我們開始今天的算法題：鏡像二叉樹，就是將一顆二叉樹上的左右節(jié)點全部交換，就好比鏡子里的二叉樹，左右方向是反過來的。
二叉樹節(jié)點表示
class Node<T> {
T value;
Node<T> left;
Node<T> right;
Node(T value) {
this.value = value;
}
Node(T value, Node<T> left, Node<T> right) {
this.value = value;
this.left = left;
this.right = right;
}
}
一個參數的構造器是葉子節(jié)點，三個參數的構造器是中間節(jié)點，看到這里讀者應該知道這是 Java 語言，我使用了范型
構造二叉樹
Node<Integer> node2 = new Node<>(2);
Node<Integer> node3 = new Node<>(3);
Node<Integer> node1 = new Node<>(1, node2, node3);
// 一次性構造
Node<Integer> node1 = new Node<>(1, new Node<>(2), new Node<>(3));
如果我們正確寫出了鏡像算法，那如何來直觀驗證鏡像的結構是否正確呢？LeetCode 使用的是單元測試，它使用一系列的單元測試和壓力測試腳本代碼來驗證用戶編寫的算法的正確性和性能。但是我們不要這樣做，因為不直觀。我們選擇對二叉樹的結構內容進行直觀的呈現，如此就可以使用肉眼來進行快速驗證。如何直觀呈現呢？我們使用最簡單的括號表示法，它并不是最直觀的，但是它易于實現。
class Node<T> {
T value;
Node<T> left;
Node<T> right;
public String toString() {
// 葉節(jié)點
if (left == right) {
return String.format("[%d]", value);
}
// 中間節(jié)點
return String.format("(%d, %s, %s)", value, left, right);
}
}
Node<Integer> node2 = new Node<>(2);
Node<Integer> node3 = new Node<>(3);
Node<Integer> 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<T> node) {
// 葉子結點
if (node.left == node.right) {
return;
}
// 遞歸鏡像左子樹
if (node.left != null)
mirrorFrom(node.left);
// 遞歸鏡像右子樹
if (node.right != null)
mirrorFrom(node.right);
// 交換當前節(jié)點的左右子樹
Node<T> tmp = node.left;
node.left = node.right;
node.right = tmp;
}
遞歸算法的優(yōu)勢在于邏輯簡單，缺點在于每一次遞歸調用函數都會增加一個新的函數堆棧，如果樹的深度太深，函數的堆棧內存就會持續(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<T> mirrorByLoop() {
// 空樹不必處理
if (root == null) {
return this;
}
// 當前循環(huán)需要處理的節(jié)點
LinkedList<Node<T>> expandings = new LinkedList<>();
expandings.add(root);
// 沒有后臺節(jié)點就可以終止循環(huán)
while (!expandings.isEmpty()) {
// 下一次循環(huán)需要處理的節(jié)點
// 也就是當前節(jié)點的所有兒子節(jié)點
LinkedList<Node<T>> nextExpandings = new LinkedList<>();
// 遍歷處理當前層的所有節(jié)點
for (Node<T> node : expandings) {
// 將后代節(jié)點收集起來，留著下一次循環(huán)
if (node.left != null) {
nextExpandings.add(node.left);
}
if (node.right != null) {
nextExpandings.add(node.right);
}
// 交換當前節(jié)點的左右指針
Node<T> 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<T> {
static class Node<T> {
T value;
Node<T> left;
Node<T> right;
Node(T value) {
this.value = value;
}
Node(T value, Node<T> left, Node<T> 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<T> root;
public MirrorBinaryTree(Node<T> root) {
this.root = root;
}
public MirrorBinaryTree<T> mirrorByLoop() {
if (root == null) {
return this;
}
LinkedList<Node<T>> expandings = new LinkedList<>();
expandings.add(root);
while (!expandings.isEmpty()) {
LinkedList<Node<T>> nextExpandings = new LinkedList<>();
for (Node<T> node : expandings) {
if (node.left != null) {
nextExpandings.add(node.left);
}
if (node.right != null) {
nextExpandings.add(node.right);
}
Node<T> tmp = node.left;
node.left = node.right;
node.right = tmp;
}
expandings = nextExpandings;
}
return this;
}
public MirrorBinaryTree<T> mirrorByRecursive() {
mirrorFrom(root);
return this;
}
public void mirrorFrom(Node<T> node) {
if (node.left == node.right) {
return;
}
if (node.left != null)
mirrorFrom(node.left);
if (node.right != null)
mirrorFrom(node.right);
Node<T> 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<Integer> 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<Integer> 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]))
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業(yè)資訊頻道，感謝您對億速云的支持。
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
