LeetCode 226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
 

解法一：

递归：交换左右子树的指针。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)return nullptr;
        TreeNode* temp=root->left;
        root->left=invertTree(root->right);
        root->right=invertTree(temp);
        return root;
    }
};

解法二：辅助栈

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* u=s.top();
            s.pop();
            if(!u)
                continue;
            TreeNode *temp=u->left;
            u->left=u->right;
            u->right=temp;
            s.push(u->left);
            s.push(u->right);
        }
        return root;
    }
};