溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
給出一棵二叉樹，求它的鏡像，如下圖：右邊是二叉樹是左邊二叉樹的鏡像。
仔細分析這兩棵樹的特點，看看能不能總結出求鏡像的步驟。這兩棵樹的根節點相同，但他們的左右兩個子節點交換了位置。因此我們不妨先在樹中交換根節點的兩個子節點，就得到了下面一幅圖中的第二顆樹
解法1（遞歸）
思路1：如果當前節點為空，返回，否則交換該節點的左右節點，遞歸的對其左右節點進行交換處理。
/*class TreeNode{
int val;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val) {
this.val = val;
}
}*/
public static void mirrorTree(TreeNode root)
{
if(root==null)
return;
//交換該節點指向的左右節點。
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
//對其左右孩子進行鏡像處理。
mirrorTree(root.left);
mirrorTree(root.right);
}
交換過程如下圖：
交換根節點的兩個子節點之后，我們注意到值為10，6的結點的子節點仍然保持不變，因此我們還需要交換這兩個結點的左右子節點。交換之后的結果分別為第三課樹和第四顆樹。做完這兩次交換之后，我們已經遍歷完所有的非葉子結點。此時交換之后的樹剛好就是原始樹的鏡像。
思路2：如果當前節點為 null，返回 null ，否則先分別對該節點的左右孩子進行鏡像處理，然后將該節點的左指針指向右孩子，右指針指向左孩子，對該節點進行鏡像處理。
/*class TreeNode{
int val;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val) {
this.val = val;
}
}*/
public static TreeNode mirrorTree1(TreeNode root)
{
if(root==null)
return null;
//對左右孩子鏡像處理
TreeNode left=mirrorTree1(root.left);
TreeNode right=mirrorTree1(root.right);
//對當前節點進行鏡像處理。
root.left=right;
root.right=left;
return root;
}
解法2（非遞歸）
思路1：層次遍歷，根節點不為 null 將根節點入隊，判斷隊不為空時，節點出隊，交換該節點的左右孩子，如果左右孩子不為空，將左右孩子入隊。
public static void mirrorTreeWithQueue(TreeNode root)
{
if(root==null)
return;
//如果樹為 null 直接返回。否則將根節點入隊列。
Queue<TreeNode> queue= new LinkedList<TreeNode>() ;
queue.add(root);
while(!queue.isEmpty())
{
//隊列不為空時，節點出隊，交換該節點的左右子樹。
TreeNode root1=queue.poll();
/*TreeNode left,right;
left=root1.left;
right=root1.right;
root1.right=left;
root1.left=right;
*/
Swap(root);
if(root1.right!=null)
{
queue.add(root1.right);
//如果左子樹不為 null 入隊
}
if(root1.left!=null)
{
queue.add(root1.left);
//如果右子樹不為 null 入隊。
}
}
}
public static void Swap(TreeNode root)
{
TreeNode temp;
temp=root.right;
root.right=root.left;
root.left=temp;
}
思路2：先序遍歷，如果根節點不為 null 將根節點入棧，當棧不為 null 出棧，交換左右節點，如果左右節點不為 null 入棧。
public static void mirrorTreeWithStack(TreeNode root)
{
if(root==null)
return;
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty())
{
//當棧不為 null 時出棧，交換左右子樹。
TreeNode root1=stack.pop();
/*TreeNode left,right;
left=root1.left;
right=root1.right;
root1.right=left;
root1.left=right;*/
Swap(root);
if(root1.right!=null)
{
//右子樹不為 null 入棧
stack.push(root1.right);
}
if(root1.left!=null)
{
//左子樹不為 null 入棧
stack.push(root1.left);
}
}
}
public static void Swap(TreeNode root)
{
TreeNode temp;
temp=root.right;
root.right=root.left;
root.left=temp;
}
總結
以上就是本文關于Java編程求二叉樹的鏡像兩種方法介紹的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站：
java算法實現紅黑樹完整代碼示例
Java 蒙特卡洛算法求圓周率近似值實例詳解
java實現的各種排序算法代碼示例
如有不足之處，歡迎留言指出。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
