翻转二叉树

LeetCode 226 · Easy · 1 min · 榎aaaa

以前序遍历为例，从根节点开始，逐步交换左右子树（先交换左子树，后交换右子树），直到所有叶子节点都交换完毕；后序遍历同理，先把左子树的所有节点交换完毕，再处理右子树，最后在root节点处将整个左右子树交换

而中序遍历是个特例，它会先交换左子树的所有节点，然后逐层返回到最顶部的root节点，将左子树和右子树交换，此时如果按照之前的逻辑，继续对右子树进行交换的话，相当于是对一开始的左子树又进行了一次交换，所有此时需要改变一下代码，进行对左子树）也就是一开始的右子树）进行交换，这样才能得到正确的结果

 1// 前序
 2TreeNode* invertTree(TreeNode* root)
 3{
 4    if(root == nullptr) return nullptr;
 5    std::swap(root->left, root->right);
 6    invertTree(root->left);
 7    invertTree(root->right);
 8
 9    return root;
10}
11
12// 中序
13TreeNode* invertTree(TreeNode* root)
14{
15    if(root == nullptr) return nullptr;
16    invertTree(root->left);
17    std::swap(root->left, root->right);
18    invertTree(root->left);
19
20    return root;
21}
22
23// 后序
24TreeNode* invertTree(TreeNode* root)
25{
26    if(root == nullptr) return nullptr;
27    invertTree(root->left);
28    invertTree(root->right);
29    std::swap(root->left, root->right);
30
31    return root;
32}