扣丁學(xué)堂Java培訓(xùn)之求二叉樹的鏡像方法及源碼分享

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

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

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

解法1（遞歸）

思路1：如果當(dāng)前節(jié)點(diǎn)為空，返回，否則交換該節(jié)點(diǎn)的左右節(jié)點(diǎn)，遞歸的對(duì)其左右節(jié)點(diǎn)進(jìn)行交換處理。

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

交換過程如下圖：

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

思路2：如果當(dāng)前節(jié)點(diǎn)為null，返回null，否則先分別對(duì)該節(jié)點(diǎn)的左右孩子進(jìn)行鏡像處理，然后將該節(jié)點(diǎn)的左指針指向右孩子，右指針指向左孩子，對(duì)該節(jié)點(diǎn)進(jìn)行鏡像處理。

　　/*classTreeNode{
　　intval;
　　TreeNodeleft=null;
　　TreeNoderight=null;
　　publicTreeNode(intval){
　　this.val=val;
　　}
　　}*/
　　publicstaticTreeNodemirrorTree1(TreeNoderoot)
　　{
　　if(root==null)
　　returnnull;
　　//對(duì)左右孩子鏡像處理
　　TreeNodeleft=mirrorTree1(root.left);
　　TreeNoderight=mirrorTree1(root.right);
　　//對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行鏡像處理。
　　root.left=right;
　　root.right=left;
　　returnroot;
　　}

解法2（非遞歸）

思路1：層次遍歷，根節(jié)點(diǎn)不為null將根節(jié)點(diǎn)入隊(duì)，判斷隊(duì)不為空時(shí)，節(jié)點(diǎn)出隊(duì)，交換該節(jié)點(diǎn)的左右孩子，如果左右孩子不為空，將左右孩子入隊(duì)。

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

思路2：先序遍歷，如果根節(jié)點(diǎn)不為null將根節(jié)點(diǎn)入棧，當(dāng)棧不為null出棧，交換左右節(jié)點(diǎn)，如果左右節(jié)點(diǎn)不為null入棧。

　　publicstaticvoidmirrorTreeWithStack(TreeNoderoot)
　　{
　　if(root==null)
　　return;
　　Stack<TreeNode>stack=newStack<TreeNode>();
　　stack.push(root);
　　while(!stack.isEmpty())
　　{
　　//當(dāng)棧不為null時(shí)出棧，交換左右子樹。
　　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;
　　}

以上就是本文關(guān)于Java編程求二叉樹的鏡像兩種方法介紹的全部?jī)?nèi)容，希望對(duì)大家有所幫助，最后想要了解更多Java信息的同學(xué)可以前往扣丁學(xué)堂官網(wǎng)咨詢，扣丁學(xué)堂Java培訓(xùn)深受學(xué)員的喜愛。扣丁學(xué)堂不僅有專業(yè)的老師和與時(shí)俱進(jìn)的課程體系，還有大量的Java視頻教程供學(xué)員觀看學(xué)習(xí)哦。扣丁學(xué)堂java技術(shù)交流群：487098661。微 信 號(hào)：codingbb