递归-相信函数!

今天刷 hot-100 的时候刷到了这么一道题(226. 翻转二叉树):

思考半天怎么模拟最后突然想到这个东西好像可以递归,我们假定并且相信这个函数已经完成了它的功能,即使用 root 调用它它就能返回 root 的已经翻转好了的二叉树,那么对于当前 root 来说,我们可以直接调用得到 root 的 l 和 r 已经翻转好的子树,然后再手动把这两个子树完成翻转就好了

---

/**
 * 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 == nullptr) return nullptr;
        if(root->left!=nullptr) root->left = invertTree(root->left);
        if(root->right!=nullptr) root->right = invertTree(root->right);
        swap(root->left,root->right);
        return root;
    }
};

---

你相信它,它在递归调用的时候一步步往前走,每一步都在你的相信下完成”当前 root 的左右子树翻转功能”,那么最后从整体看你就完成了整个二叉树的翻转.你相信,它实现!