HOT力扣100（43）二叉树-翻转二叉树

要翻转以 root 为根的树先分别翻转 root 的左子树和右子树然后把 root 的左指针指向翻转后的右子树右指针指向翻转后的左子树。这是典型的后序遍历思路先处理左子树递归翻转左子树再处理右子树递归翻转右子树最后处理当前节点交换左右指针完整解题步骤递归终止条件如果当前节点是空节点root nullptr直接返回nullptr空树不用翻转。递归翻转左子树调用invertTree(root-left)得到翻转后的左子树的根节点。递归翻转右子树调用invertTree(root-right)得到翻转后的右子树的根节点。交换当前节点的左右指针把当前节点的左孩子指向翻转后的右子树右孩子指向翻转后的左子树。返回当前节点作为翻转后的子树的根节点返回给上一层递归/** * 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; } TreeNode* left invertTree(root-left); TreeNode* right invertTree(root-right); root-left right; root-right left; return root; } };