FilesExpand file tree

 master

/

reverseBinaryTree.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

57 lines (56 loc) · 1.37 KB

 master

/

reverseBinaryTree.cpp

Top

File metadata and controls

• Code
• Blame

57 lines (56 loc) · 1.37 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

/*

* 题：操作给定的二叉树，将其变换为源二叉树的镜像

* 二叉树的镜像定义：源二叉树 镜像二叉树

* 8 8

* / \ / \

* 6 10 10 6

* / \ / \ / \ / \

* 5 7 9 11 11 9 7 5

* struct TreeNode{

* int val;

* struct TreeNode* left;

* struct TreeNode* right;

* TreeNode(int x):

* val(x), left(NULL),right(NULL){}

* };

*/

class solution{

public:

//递归解法

void Mirror(TreeNode* pRoot){

if(!pRoot)

return;

//反转左右子结点

TreeNode* p=pRoot->left;

pRoot->left=pRoot->right;

pRoot->right=p;

//递归反转左右子树

Mirror(pRoot->left);

Mirror(pRoot->right);

}

};

class solution{

public:

void Mirror(TreeNode* pRoot){

if(!pRoot)

return;

stack<TreeNode*> nodeStack;

nodeStack.push(pRoot); //根结点进栈

while(!nodeStack.empty()){

TreeNode* p=nodeStack.top(); //获取栈顶元素，然后pop

nodeStack.pop();

//如果当前结点的左右子树不全为空，则反转

//可以避免处理叶子结点的开销

if(p->left||p->right){

TreeNode* tmp=p->left;

p->left=p->right;

p->right=tmp;

}

//叶子结点不需要反转

if(p->left)

nodeStack.push(p->left);

if(p->right)

nodeStack.push(p->right);

}

}

}