226以翻转二叉树来举例子讲清楚递归

很多时候拿到递归题看到代码不清楚这个代码该如何运行，是先执行哪句后执行哪句，这篇将以这个题目为例，将清楚递归中我不明白的地方。

/** * Definition for a binary tree node. * 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) {} * }; */ class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==NULL){ return nullptr; } TreeNode* left=invertTree(root->left); TreeNode* right=invertTree(root->right); root->left=right; root->right=left; return root; } };

首先，我们先处理头节点的左节点，也就是2。然后以2为头节点，处理2的左节点1，然后以1为头节点，发现他是空，所有我们返回NULL。然后继续来到我们的上一个头节点2，处理他的右节点也就是3，我们发现他也是空，所有我们也返回NULL。然后执行下面的代码交换1与3的位置。然后又继续返回到上一个头节点也就是4，我们现在要来处理他的右节点也就是7，用上述方法处理下去就可以了。

现在我们将代码这个递与归好好拆分成一块一块的代码。

先递到节点1： TreeNode* invertTree_1(TreeNode* root) { if (root == NULL) return nullptr; // 节点1不为空，跳过 // 左孩子为空，直接返回nullptr TreeNode* left = invertTree(root->left); // 右孩子为空，直接返回nullptr TreeNode* right = invertTree(root->right); // 交换左右孩子（都是空，无变化） root->left = right; root->right = left; return root; // 返回节点1 } 递到节点3： TreeNode* invertTree_3(TreeNode* root) { if (root == NULL) return nullptr; // 节点3不为空，跳过 TreeNode* left = invertTree(root->left); // 左空，返回nullptr TreeNode* right = invertTree(root->right); // 右空，返回nullptr root->left = right; root->right = left; return root; // 返回节点3 } 递到节点2： TreeNode* invertTree_2(TreeNode* root) { if (root == NULL) return nullptr; // 节点2不为空，跳过 // 递：递归翻转左子树（节点1），返回节点1 TreeNode* left = invertTree(root->left); // 递：递归翻转右子树（节点3），返回节点3 TreeNode* right = invertTree(root->right); // 归：交换左右孩子 root->left = right; // 左孩子变成节点3 root->right = left; // 右孩子变成节点1 return root; // 返回翻转后的节点2 }