欧美成人午夜免费全部完,亚洲午夜福利精品久久,а√最新版在线天堂,另类亚洲综合区图片小说区,亚洲欧美日韩精品色xxx

Java開發(fā)編程求二叉樹的鏡像兩種方法介紹及源碼解決思路

2018-04-09 10:05:27 1278瀏覽

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

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

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

解法1（遞歸）

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

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

交換過程如下圖：

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

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

　　/*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);
　　//對當前節(jié)點進行鏡像處理。
　　root.left=right;
　　root.right=left;
　　returnroot;
　　}

解法2（非遞歸）

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

　　publicstaticvoidmirrorTreeWithQueue(TreeNoderoot)
　　{
　　if(root==null)
　　return;
　　//如果樹為null直接返回。否則將根節(jié)點入隊列。
　　Queue<TreeNode>queue=newLinkedList<TreeNode>();
　　queue.add(root);
　　while(!queue.isEmpty())
　　{
　　//隊列不為空時，節(jié)點出隊，交換該節(jié)點的左右子樹。
　　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：先序遍歷，如果根節(jié)點不為null將根節(jié)點入棧，當棧不為null出棧，交換左右節(jié)點，如果左右節(jié)點不為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;
　　}

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

【關(guān)注微信公眾號獲取更多學習資料】

查看更多關(guān)于“Java開發(fā)資訊”的相關(guān)文章>>