1.题目
2.思路
基础递归题。
可以直接后序遍历(前序也可),递归到底后就交换左右孩子(叶结点),再往二叉树上返回。
前序和后序唯一的区别是:
前序遍历:将「处理当前节点」放到「递归左子树」之前。
后序遍历:将「处理当前节点」放到「递归右子树」之后。
3.代码
/** * 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 root;//遍历到null节点时,不用翻转,直接返回它本身 } TreeNode* leftchild=invertTree(root->left); TreeNode* rightchild=invertTree(root->right); root->left=rightchild; root->right=leftchild; return root; } };
4.复杂度
(1)时间复杂度:O ( N ) O(N)O(N),遍历每个结点(N个结点)。
(2)空间复杂度:O ( l o g N ) O(logN)O(logN),递归栈高度即二叉树高度。