深入理解反轉二叉樹

二叉樹是一種重要的數據結構，常用於搜索、排序、計算等領域。反轉二叉樹指將所有節點的左右子樹交換，即對於原二叉樹中的任意一個節點，如果其左子樹不空，則交換左右子樹，如果其右子樹不為空，則交換左右子樹。反轉二叉樹是一道經典的面試題，也是實際開發中常用到的技巧。

一、遞歸實現反轉二叉樹

將左右子樹交換可以看成是對節點的一次操作，所以遞歸是一個自然的選擇。遞歸方法的主要思路是對於根節點，先交換其左右子樹，然後對左右子樹分別遞歸調用反轉函數。

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}

代碼實現簡單明了，先判斷根節點是否為空，如果不為空，交換其左右子樹，並分別遞歸調用其左右子節點。

二、迭代實現反轉二叉樹

遞歸實現的思路簡單，但有可能會爆棧。為了避免這種情況發生，我們可以使用循環迭代的方法實現反轉二叉樹。迭代方法需要藉助棧來實現，對於每一個節點，我們將其左右子節點交換後，將其放入棧中，然後從棧中取出節點並重複上述操作，直至棧為空。

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Stack stack = new Stack();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return root;
}

代碼實現中，我們使用了標準的棧數據結構來存儲每個節點，並依次取出節點。對於每個節點，交換左右子樹，然後分別將左右子節點入棧。重複上述步驟，直至棧為空。

三、反轉二叉樹的應用

反轉二叉樹是一個簡單而又實用的技巧，可以用於多種應用場景。以下是其中的兩個例子：

1. 獲取二叉樹的鏡像

二叉樹的鏡像是指以根節點為對稱軸，交換其左右子樹後得到的新二叉樹。獲取二叉樹的鏡像可以直接使用反轉二叉樹的方法實現。

TreeNode mirror(TreeNode root) {
    return invertTree(root);
}

2. 判斷兩個二叉樹是否相同

判斷兩個二叉樹是否相同，可以通過先將兩個二叉樹反轉，然後依次比較它們的每個節點是否相同，即可得出結論。

public boolean isSameTree(TreeNode p, TreeNode q) {
    TreeNode t1 = invertTree(p);
    TreeNode t2 = invertTree(q);
    return isSame(t1, t2);
}
private boolean isSame(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    if (p.val != q.val) return false;
    return isSame(p.left, q.left) && isSame(p.right, q.right);
}

總結

通過本文，我們詳細介紹了反轉二叉樹的實現方法以及其在實際應用中的作用。熟練掌握反轉二叉樹的方法可以幫助我們更好地理解二叉樹的基本操作，提高我們的編程技巧。