Invert Binary Tree
Total Accepted: 54994 Total Submissions: 130742 Difficulty: Easy
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
通过这道题，好好理解了递归。
递归返回的是什么要考虑清楚，
可以仔细研磨这道题，很好的题。
C语言
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL)
return root;
if (root->left == NULL && root->right == NULL)
return root;
else{
struct TreeNode* temp = root->right;
root->right = root->left;
root->left = temp;
}
root->left = invertTree(root->left);
root->right = invertTree(root->right); return root;
}
下面是在网上找的一种解法，C++写的。由于这是对实际树的结构进行操作，所以说可以不特别管返回值。
TreeNode* invertTree(TreeNode* root) {
if (root) {
invertTree(root->left);
invertTree(root->right);
std::swap(root->left, root->right);
}
return root;
}