226. Invert Binary Tree

1. 问题描述

Invert a binary tree.

Tag: Tree

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

2. 解题思路

3. 代码

 1 class Solution 
 2 {
 3 public:
 4     TreeNode* invertTree(TreeNode* root)//递归实现
 5     {
 6         if (NULL == root)
 7         {
 8             return root;
 9         }
10         if (NULL != root->left && NULL != root->right)
11         {
12             TreeNode *pt = root->right;
13             root->right = root->left;
14             root->left = pt;
15             invertTree(root->left);
16             invertTree(root->right);
17             return root;
18         }
19     }
20     TreeNode* invertTree2(TreeNode* root)//递归实现
21     {
22         if (NULL == root)
23         {
24             return root;
25         } 
26         TreeNode *pt = root->left;  
27         root->left = invertTree2(root->right);  
28         root->right = invertTree2(pt);  
29         return root; 
30     }
31     TreeNode* invertTree3(TreeNode* root)//非递归方式：利用栈实现
32     {
33         if(NULL == root) 
34         {
35             return NULL;
36         }
37         std::stack<TreeNode *> tSta;
38         tSta.push(root);
39         while (!tSta.empty())
40         {            
41             TreeNode *pCur = tSta.top();
42             tSta.pop();
43             TreeNode *pt = pCur->left;
44             pCur->left = pCur->right;
45             pCur->right = pt;
46             if (NULL != pCur->left)
47             {
48                 tSta.push(pCur->left);
49             }
50             if (NULL != pCur->right)
51             {
52                 tSta.push(pCur->right);
53             }            
54         }
55         return root;  
56     }
57 };

226. Invert Binary Tree

1. 问题描述

2. 解题思路

3. 代码

4. 反思