递归实现:
1 /** 2 * Definition of TreeNode: 3 * class TreeNode { 4 * public: 5 * int val; 6 * TreeNode *left, *right; 7 * TreeNode(int val) { 8 * this->val = val; 9 * this->left = this->right = NULL; 10 * } 11 * } 12 */ 13 class Solution { 14 public: 15 /** 16 * @param root: a TreeNode, the root of the binary tree 17 * @return: nothing 18 */ 19 void invertBinaryTree(TreeNode *root) { 20 // write your code here 21 if (!root) return; 22 swap(root -> left, root -> right); 23 invertBinaryTree(root -> left); 24 invertBinaryTree(root -> right); 25 } 26 };
迭代实现:
1 /** 2 * Definition of TreeNode: 3 * class TreeNode { 4 * public: 5 * int val; 6 * TreeNode *left, *right; 7 * TreeNode(int val) { 8 * this->val = val; 9 * this->left = this->right = NULL; 10 * } 11 * } 12 */ 13 class Solution { 14 public: 15 /** 16 * @param root: a TreeNode, the root of the binary tree 17 * @return: nothing 18 */ 19 void invertBinaryTree(TreeNode *root) { 20 // write your code here 21 if (!root) return; 22 queue<TreeNode*> level; 23 level.push(root); 24 while (!level.empty()) { 25 TreeNode* node = level.front(); 26 level.pop(); 27 swap(node -> left, node -> right); 28 if (node -> left) level.push(node -> left); 29 if (node -> right) level.push(node -> right); 30 } 31 } 32 };