题目解析:
题目链接:https://leetcode.com/problems/invert-binary-tree/description/
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
解题思路:
好吧,我承认写这个纯粹是因为Google拒绝Max Howell的恶趣味。题目本身不算难,了解二叉树多一点就知道咋做。
思路一:新建一棵树,将原树的遍历顺序和建树的相反,然后赋值就OK。
思路二:直接原地调换左右子树。我刚开始做的时候,用两个指针遍历这棵树,调换左右子树的值,因为天真的以为给的会是全完平衡的二叉树,后来发现不对。然后就用直接调换左右子树了。
思路一;
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
TreeNode* root1;
invert(root,root1);
return root;
}
void invert(TreeNode* root,TreeNode* root1)
{
if(!root)
{
root1 = root;
return ;
}
root1 = new TreeNode(0);
root1->val = root->val;
invert(root->right,root1->left);
invert(root->left,root1->right);
}
};
思路二:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
//TreeNode* root1;
invert(root,root);
return root;
}
void invert(TreeNode* root,TreeNode* root1)
{
if(!root)
{
//root1 = root;
return ;
}
//root1 = new TreeNode(0);
swap(root1->right, root->left);
invert(root->left,root1->left);
invert(root->right,root1->right);
}
};