https://leetcode.cn/problems/invert-binary-tree/description/
算法思想:
先从root结点开始,递归的对树进行遍历,知道找到叶子节点后从叶子结点开始翻转
如果当前遍历到的结点root的左右两棵子树都已经完成翻转,则只需要交换两棵子树的位置,即可完成当前的root结点的两棵子树的交换
后面继续递归下去,即可完成整棵子树的交换
/**
* 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 0;
}
TreeNode *left = invertTree(root->left);
TreeNode *right = invertTree(root->right);
// 此时:找到了当前遍历到的叶子节点的根结点,完成其左右两棵子树的交换
root->left = right;
root->right = left;
return root;
}
};