leetcode_226解题思路（二叉树翻转）

题意：实现二叉树的翻转。两种解题意思：一、根据树遍历方式的特点先创建一个二叉树；二、在原树上直接交换每一级的左右子树实现翻转

#include<iostream>
using namespace std;

//definition for a binary tree node.
typedef struct treenode {
int val;
treenode* left;
treenode* right;
treenode() : val(0), left(nullptr), right(nullptr) {}
treenode(int x) : val(x), left(nullptr), right(nullptr) {}
treenode(int x, treenode* left, treenode* right) : val(x), left(left), right(right) {}
}TreeNode;

//方法一：参考二叉树对称题目（leetcode_101)的方法，反转链表
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
//if (!root) return root;
TreeNode* result=root;
preorderTraverse(root, result);
return result;
}
void preorderTraverse(TreeNode*& origin, TreeNode*& invert);
};

void Solution::preorderTraverse(TreeNode*& origin, TreeNode*& invert)
{
if (origin) {
invert = new TreeNode(origin->val);
preorderTraverse(origin->left, invert->right);
preorderTraverse(origin->right, invert->left);
}
return;
}

//方法二：网友法，直接二叉树每层交换翻转法
class Solution {
public:
void invert(TreeNode* root)
{
if (root == NULL)
return;
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
invert(root->left);
invert(root->right);
}
TreeNode* invertTree(TreeNode* root) {
invert(root);
return root;
}
};