leetcode刷题|【LeetCode】NO.226.翻转二叉树的一次负负得正还能AC的调试画图分析算法|二叉树|递归算法|leetcod

前言前几天朋友在群里发了张图：简单来说，负负得正

文章图片

当时感觉挺好笑的，结果今天就被我碰上了。
LeetCode.NO.226.翻转二叉树

Given the root of a binary tree, invert the tree, and return its root.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree

文章图片

想好一会儿，给了一种很烦的递归思路：

void Swap(struct TreeNode* root) {struct TreeNode* tmp = root->left; root->left = root->right; root->right = tmp; } void _invertTree(struct TreeNode* root, struct TreeNode* left, struct TreeNode* right) {if(left == NULL && right == NULL) {return; } if(left != NULL && right != NULL) {_invertTree(left, left->left, left->right); _invertTree(right, right->left, right-> right); Swap(root); } if(left == NULL && right != NULL) {_invertTree(right, right->left, right-> right); Swap(root); } //上一句结束后，进行了一次Swap，left不是变成right，right不是变成left了？那下面的if应该执行下去！? if(left != NULL && right == NULL) {_invertTree(left, left->left, left->right); Swap(root); } }struct TreeNode* invertTree(struct TreeNode* root) {if(root == NULL) return root; _invertTree(root, root->left, root->right); return root; }

提交之后，过了
但是又看了看，看出了问题：

if(left == NULL && right != NULL) {_invertTree(right, right->left, right-> right); Swap(root); } //上一句结束后，left不是变成right，right不是变成left了？那下面的if应该执行下去！? if(left != NULL && right == NULL) {_invertTree(left, left->left, left->right); Swap(root); }

第一次Swap，left不是变成right，right不是变成left了？那下面的if还应该执行下去！?可是我们应该让这次递归结束，不能再去交换了啊！！但是他错误地交换了之后，为什么还能AC？？？
理应这么写，每次Swap后，return跳出当前递归

if(left == NULL && right != NULL) {_invertTree(right, right->left, right-> right); Swap(root); return; } if(left != NULL && right == NULL) {_invertTree(left, left->left, left->right); Swap(root); }

我怎么也看不出来，为什么没return还能过。
研究过程我们打开VS，只能自己写好测试用例，调试！！！
【leetcode刷题|【LeetCode】NO.226.翻转二叉树的一次负负得正还能AC的调试画图分析】测试用例长这样：

文章图片

#define _CRT_SECURE_NO_WARNINGS 1 #include #include typedef struct BTNode { struct BTNode* right; struct BTNode* left; int val; }BTNode; BTNode* BTNodeCreate(int x) { BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root->val = x; root->left = NULL; root->right = NULL; return root; }void Swap(struct BTNode* root) {struct BTNode* tmp = root->left; root->left = root->right; root->right = tmp; } void _invertTree(struct BTNode* root, struct BTNode* left, struct BTNode* right) {if (left == NULL && right == NULL) {return; } if (left != NULL && right != NULL) {_invertTree(left, left->left, left->right); _invertTree(right, right->left, right->right); Swap(root); } if (left == NULL && right != NULL) {_invertTree(right, right->left, right->right); Swap(root); } if (left != NULL && right == NULL) {_invertTree(left, left->left, left->right); Swap(root); } }struct BTNode* invertTree(struct BTNode* root) {if (root == NULL) return root; _invertTree(root, root->left, root->right); return root; } int main() { BTNode* node1 = BTNodeCreate(1); BTNode* node2 = BTNodeCreate(2); BTNode* node3 = BTNodeCreate(3); node1->right = node2; node2->right = node3; invertTree(node1); return 0; }

再把这段有异议的代码拿出来：

if (left == NULL && right != NULL) {_invertTree(right, right->left, right->right); Swap(root); } /*位置1*/ if (left != NULL && right == NULL) {_invertTree(left, left->left, left->right); Swap(root); }

我们在位置1处停下。
那么按照我的理解，此时：

left == val为3的节点
right == NULL
root->left == val为3的节点
root->right == NULL

监视：

文章图片

root->left 和 root->right 确实交换了，但left和right没有交换！！！
原来问题出在这里：

left 和 right 是一份root->left 和 root->right的临时拷贝，root->left和root-right确实交换了，但身为临时拷贝的left和right还是没交换，该是谁就还是谁！所以下面 if 语句根本就不会进去！

本题优化解答这个递归写的有点长，因为又用了一个子函数_invertTree,我们试着不用子函数来做一下，让代码少一点

struct TreeNode* invertTree(struct TreeNode* root){if(!root) return NULL; struct TreeNode* left = root->left; struct TreeNode* right = root->right; root->right = invertTree(left); root->left = invertTree(right); return root; }