操作給定的二叉樹，將其變換為源二叉樹的鏡像，假設題目所給的二叉樹如下所示
解法一
思路很簡單，既然要求鏡像，只要將每一個結點的左右子結點交換一下位置就好了，使用中序遍歷可以幫助我們實作這一想法
public class Solution {
private TreeNode temp;
public void Mirror(TreeNode root) {
if(root == null) {
return;
}
temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
}
解法二
解法一雖然簡單粗暴，但如果碰到大資料就直接炸了，我們還是使用遞回的思想，思考遞回的時候不要一步步看它執行了啥，思考的方式應該是首先假設子問題都已經完美處理，然后只需要處理最終的問題即可，子問題的處理方式與最終那個處理方式一樣，但是問題規模一定要逐漸縮小，最后給一個遞回出口條件即可
對于本題，首先假設 root 的左右子樹已經都處理好了，即左子樹自身已經鏡像了，右子樹自身也鏡像了，那么最后一步就是交換左右子樹，問題解決，下面進入遞回，就是處理子問題，子問題的處理方式與 root 一樣，只是要縮小問題規模，所以只需要考慮 root.left 是什么情況，root.right 是什么情況即可
public class Solution {
public void Mirror(TreeNode root) {
// 為空則結束
if(root == null) {
return;
}
// 假設 root 的左右子樹都已經完成鏡像了
// 那就讓左右子樹交換
swap(root);
// 左子樹做鏡像操作
Mirror(root.left);
// 右子樹做鏡像操作
Mirror(root.right);
}
private void swap(TreeNode node) {
TreeNode temp = null;
temp = node.left;
node.left = node.right;
node.right = temp;
}
}
當然，也可以使用堆疊來模擬上面的程序，開始執行方法時入堆疊，方法執行完畢時出堆疊
import java.util.Stack;
public class Solution {
private Stack<TreeNode> stack = new Stack<>();
public void Mirror(TreeNode root) {
if(root == null) {
return;
}
stack.push(root);
while(!stack.empty()) {
TreeNode node = stack.pop();
swap(node);
if(node.left != null) {
stack.push(node.left);
}
if(node.right != null) {
stack.push(node.right);
}
}
}
private void swap(TreeNode node) {
TreeNode temp = null;
temp = node.left;
node.left = node.right;
node.right = temp;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/159507.html
標籤：其他
上一篇：LeetCode：最長回文字串