給出一棵二叉樹，求它的鏡像，如下圖：右邊是二叉樹是左邊二叉樹的鏡像。
仔細分析這兩棵樹的特點，看看能不能總結出求鏡像的步驟。這兩棵樹的根節點相同，但他們的左右兩個子節點交換了位置。因此我們不妨先在樹中交換根節點的兩個子節點，就得到了下面一幅圖中的第二顆樹
解法1（遞歸）
思路1：如果當前節點為空，返回，否則交換該節點的左右節點，遞歸的對其左右節點進行交換處理。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/*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 ，否則先分別對該節點的左右孩子進行鏡像處理，然后將該節點的左指針指向右孩子，右指針指向左孩子，對該節點進行鏡像處理。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/*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 將根節點入隊，判斷隊不為空時，節點出隊，交換該節點的左右孩子，如果左右孩子不為空，將左右孩子入隊。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
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 入棧。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
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編程求二叉樹的鏡像兩種方法介紹的全部內容，希望對大家有所幫助。如有不足之處，歡迎留言指出。
原文鏈接：http://blog.csdn.net/u013309870/article/details/69952085
