今天本文章主要介紹了Java編程求二叉樹的鏡像兩種方法介紹，分享了兩種方法，遞歸與非遞歸，每種方法又分別介紹了兩種解決思路，具有一定參考價值，需要的朋友可以了解下。

給出一棵二叉樹，求它的鏡像，如下圖：右邊是二叉樹是左邊二叉樹的鏡像。

仔細分析這兩棵樹的特點，看看能不能總結出求鏡像的步驟。這兩棵樹的根節點相同，但他們的左右兩個子節點交換了位置。因此我們不妨先在樹中交換根節點的兩個子節點，就得到了下面一幅圖中的第二顆樹

解法1（遞歸）

思路1：如果當前節點為空，返回，否則交換該節點的左右節點，遞歸的對其左右節點進行交換處理。

　　/*classTreeNode{
　　intval;
　　TreeNodeleft=null;
　　TreeNoderight=null;
　　publicTreeNode(intval){
　　this.val=val;
　　}
　　}*/
　　publicstaticvoidmirrorTree(TreeNoderoot)
　　{
　　if(root==null)
　　return;
　　//交換該節點指向的左右節點。
　　TreeNodetemp=root.left;
　　root.left=root.right;
　　root.right=temp;
　　//對其左右孩子進行鏡像處理。
　　mirrorTree(root.left);
　　mirrorTree(root.right);
　　}

交換過程如下圖：

交換根節點的兩個子節點之后，我們注意到值為10，6的結點的子節點仍然保持不變，因此我們還需要交換這兩個結點的左右子節點。交換之后的結果分別為第三課樹和第四顆樹。做完這兩次交換之后，我們已經遍歷完所有的非葉子結點。此時交換之后的樹剛好就是原始樹的鏡像。

思路2：如果當前節點為null，返回null，否則先分別對該節點的左右孩子進行鏡像處理，然后將該節點的左指針指向右孩子，右指針指向左孩子，對該節點進行鏡像處理。

　　/*classTreeNode{
　　intval;
　　TreeNodeleft=null;
　　TreeNoderight=null;
　　publicTreeNode(intval){
　　this.val=val;
　　}
　　}*/
　　publicstaticTreeNodemirrorTree1(TreeNoderoot)
　　{
　　if(root==null)
　　returnnull;
　　//對左右孩子鏡像處理
　　TreeNodeleft=mirrorTree1(root.left);
　　TreeNoderight=mirrorTree1(root.right);
　　//對當前節點進行鏡像處理。
　　root.left=right;
　　root.right=left;
　　returnroot;
　　}

解法2（非遞歸）

思路1：層次遍歷，根節點不為null將根節點入隊，判斷隊不為空時，節點出隊，交換該節點的左右孩子，如果左右孩子不為空，將左右孩子入隊。

　　publicstaticvoidmirrorTreeWithQueue(TreeNoderoot)
　　{
　　if(root==null)
　　return;
　　//如果樹為null直接返回。否則將根節點入隊列。
　　Queue<TreeNode>queue=newLinkedList<TreeNode>();
　　queue.add(root);
　　while(!queue.isEmpty())
　　{
　　//隊列不為空時，節點出隊，交換該節點的左右子樹。
　　TreeNoderoot1=queue.poll();
　　/*TreeNodeleft,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入隊。
　　}
　　}
　　}
　　publicstaticvoidSwap(TreeNoderoot)
　　{
　　TreeNodetemp;
　　temp=root.right;
　　root.right=root.left;
　　root.left=temp;
　　}

思路2：先序遍歷，如果根節點不為null將根節點入棧，當棧不為null出棧，交換左右節點，如果左右節點不為null入棧。

　　publicstaticvoidmirrorTreeWithStack(TreeNoderoot)
　　{
　　if(root==null)
　　return;
　　Stack<TreeNode>stack=newStack<TreeNode>();
　　stack.push(root);
　　while(!stack.isEmpty())
　　{
　　//當棧不為null時出棧，交換左右子樹。
　　TreeNoderoot1=stack.pop();
　　/*TreeNodeleft,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);
　　}
　　}
　　}
　　publicstaticvoidSwap(TreeNoderoot)
　　{
　　TreeNodetemp;
　　temp=root.right;
　　root.right=root.left;
　　root.left=temp;
　　}

以上就是本文關于Java編程求二叉樹的鏡像兩種方法介紹的全部內容，希望對大家有所幫助，最后想要了解更多Java信息的同學可以前往扣丁學堂官網咨詢，扣丁學堂Java培訓深受學員的喜愛。扣丁學堂不僅有專業的老師和與時俱進的課程體系，還有大量的Java視頻教程供學員觀看學習哦。扣丁學堂java技術交流群：487098661。微 信 號：codingbb