After reading the quote below the problem, you will be motivated to solve it immediately :-) Well, indeed it is also relative easy. The process of inverting a binary tree is simply 3 steps:
- Swap the
leftsubtree and therightsubtree; - Invert the
leftsubtree; - Invert the
rightsubtree.
So we immediately have the following simple recursive solution.
1 class Solution { 2 public: 3 TreeNode* invertTree(TreeNode* root) { 4 if (!root) return NULL; 5 swap(root -> left, root -> right); 6 root -> left = invertTree(root -> left); 7 root -> right = invertTree(root -> right); 8 return root; 9 } 10 };
Well, you may also want to challenge yourself to solve it iteratively. The iterative solution is basically a level-order traversal. Push all the nodes of the same level to a queue and then swap their left subtree and right subtree and iterate over their subtrees.
The code is as follows.
1 class Solution { 2 public: 3 TreeNode* invertTree(TreeNode* root) { 4 if (!root) return NULL; 5 queue<TreeNode*> level; 6 level.push(root); 7 while (!level.empty()) { 8 TreeNode* node = level.front(); 9 level.pop(); 10 swap(node -> left, node -> right); 11 if (node -> left) level.push(node -> left); 12 if (node -> right) level.push(node -> right); 13 } 14 return root; 15 } 16 };
