《剑指offer》19题自己实现求普通二叉树的镜像

为了面试，看了何海涛的《剑指Offer》19题求求普通二叉树的镜像，决定通过自己的理解实现之，话不多说，立刻贴源码

//下面是 TreeOperate 类的实现

 1 #include "BinTree.h"
 2 #include <iostream>
 3 #include <cstdlib>
 4 //This function is to be used to construct a binary tree
 5 void TreeOperate::connect(BinaryTreeNode *pRoot, BinaryTreeNode *pLeft, BinaryTreeNode *pRight){
 6     if (pRoot == NULL)
 7         abort();
 8     pRoot->m_pLeft = pLeft;
 9     pRoot->m_pRight = pRight;
10 }
11 //This function is to be used to destroy a tree and recycle space the tree used
12 void TreeOperate::destroy(BinaryTreeNode *&pRoot){
13     if (pRoot == NULL) return;
14     destroy(pRoot->m_pLeft);
15     destroy(pRoot->m_pRight);
16     delete pRoot;
17     
18 }
19 //This function is to used to print the tree nodes in the preorder
20 void TreeOperate::prePrint(BinaryTreeNode *pRoot){
21     if (pRoot == NULL) return;
22     printf("%d
", pRoot->m_nValue);
23     
24     prePrint(pRoot->m_pLeft);
25     prePrint(pRoot->m_pRight);
26 
27 }
28 //This function is ultimate. It is used to return the root whose subtrees have been swapped if necessary.
29 BinaryTreeNode *TreeOperate::mirrorTree(BinaryTreeNode *pRoot){
30     //pRoot == NULL ,which is a bad case bringing about serious problems.We have to avoid it.
31     if (pRoot == NULL) abort();
32     //The root has no subtree so there is no need to do anything.
33     if (pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL){
34         return pRoot;
35     }else{
36         // The right subtree is not null.Set the left subtree to be the mirror tree of the right subtree. 
37         if (pRoot->m_pLeft == NULL){
38             pRoot->m_pLeft = mirrorTree(pRoot->m_pRight);
39             pRoot->m_pRight = NULL;
40             return pRoot;
41         }
42         // The left subtree is not null.Set the right subtree to be the mirror tree of the left subtree. 
43         if (pRoot->m_pRight == NULL){
44             pRoot->m_pRight = mirrorTree(pRoot->m_pLeft);
45             pRoot->m_pLeft = NULL;
46             return pRoot;
47         }
48         /*
49          *Get the mirrorTrees of subtrees ,and then swap the subtrees.In this case,both of the subtrees are not null.
50          */
51         //The temporary variable is used to store the value of the root of the left subtree.The primary goal is for swapping.
52         BinaryTreeNode *pTempNode = mirrorTree(pRoot->m_pLeft);
53         pRoot->m_pLeft = mirrorTree(pRoot->m_pRight);
54         pRoot->m_pRight = pTempNode;
55         return pRoot;
56     }
57 }

//下面是测试代码，为简单起见 nodeX 的m_nValue 就是 X

#include <iostream>
#include "BinTree.h"
using namespace std;
int main(){
	//Nodes shouldn't have the same space
	BinaryTreeNode *node1 = new BinaryTreeNode;
	node1->m_nValue = 1;
	node1->m_pLeft = NULL;
	node1->m_pRight = NULL;

	BinaryTreeNode *node2 = new BinaryTreeNode;
	node2->m_nValue = 2;
	node2->m_pLeft = NULL;
	node2->m_pRight = NULL;

	BinaryTreeNode *node3 = new BinaryTreeNode;
	node3->m_nValue = 3;
	node3->m_pLeft = NULL;
	node3->m_pRight = NULL;

	BinaryTreeNode *node4 = new BinaryTreeNode;
	node4->m_nValue = 4;
	node4->m_pLeft = NULL;
	node4->m_pRight = NULL;

	BinaryTreeNode *node5 = new BinaryTreeNode;
	node5->m_nValue = 5;
	node5->m_pLeft = NULL;
	node5->m_pRight = NULL;

	BinaryTreeNode *node6 = new BinaryTreeNode;
	node6->m_nValue = 6;
	node6->m_pLeft = NULL;
	node6->m_pRight = NULL;

	BinaryTreeNode *node7 = new BinaryTreeNode;
	node7->m_nValue = 7;
	node7->m_pLeft = NULL;
	node7->m_pRight = NULL;
	// All nodes have different memory space.You'd better be sure that nodeX != nodeY before using them.
	/*
	* Connect the node you need to build a tree. The first parameter is the root.The second is the left child of the root.The
	  third is the right child of the root.
	*/
	TreeOperate::connect(node1, node2, node3);
	TreeOperate::connect(node2, node4, node5);
	TreeOperate::connect(node3, node6, node7);

	//print the tree nodes in the preorder
	TreeOperate::prePrint(node1);
	cout << "***********" << endl;
	//mirrorTree
	BinaryTreeNode *pTemp = TreeOperate::mirrorTree(node1);
	TreeOperate::prePrint(node1);
	TreeOperate::destroy(node1);

	node1 = node2 = node3 = node4 = node5 = node6 = node7 = NULL;
	system("pause");

}

　　//下面是头文件的书写，一起贴上吧

 1 #ifndef BINTREE_H
 2 #define BINTREE_H
 3 struct BinaryTreeNode{
 4     int m_nValue;
 5     BinaryTreeNode* m_pLeft;
 6     BinaryTreeNode* m_pRight;
 7 };
 8 class TreeOperate{
 9 public:
10 
11     static void connect(BinaryTreeNode *, BinaryTreeNode *, BinaryTreeNode *);
12     static void destroy(BinaryTreeNode *&);
13     static void prePrint(BinaryTreeNode *);
14     static BinaryTreeNode *mirrorTree(BinaryTreeNode *);
15 };
16 #endif

总结：递归函数的情况讨论详细和函数头的设计是至关重要的

欢迎去海涛哥的博客去看看 http://zhedahht.blog.163.com/

《剑指offer》19题自己实现求普通二叉树的镜像

相关推荐