[LeetCode] Invert Binary Tree

Invert a binary tree.

     4
   /   
  2     7
 /    / 
1   3 6   9

     4
   /   
  7     2
 /    / 
9   6 3   1

递归实现：

 1     TreeNode* invertTree(TreeNode* root) {
 2         if (root == nullptr)
 3             return nullptr;
 4 
 5         TreeNode *tmp = root->left;
 6         root->left = root->right;
 7         root->right = tmp;
 8         
 9         invertTree(root->left);
10         invertTree(root->right);
11         
12         return root;
13     }

非递归实现：

 1     TreeNode* invertTree(TreeNode* root) {
 2         if (root == nullptr)
 3             return nullptr;
 4 
 5         std::stack<TreeNode*> nodes;
 6         nodes.push(root);
 7 
 8         while(!nodes.empty()) {
 9             TreeNode *pNode = nodes.top();
10             nodes.pop();
11             
12             TreeNode *tmp = pNode->left;
13             pNode->left = pNode->right;
14             pNode->right = tmp;
15             
16             if (pNode->left)
17                 nodes.push(pNode->left);
18             if (pNode->right)
19                 nodes.push(pNode->right);
20         }
21         return root;
22     }