226. Invert Binary Tree

problem description

Invert a binary tree.

Example:

Input:

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

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

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f* off.

这有点意思

algorithm thought

这里使用递归和迭代都能做。思想就是先将左右子树翻转了，然后交换左右子树即可

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)
            return root;
        TreeNode* tmp=root->left;
        root->left=invertTree(root->right);
        root->right=invertTree(tmp);
        return root;

        //下面是迭代做法
        /*
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* t=st.top();
            st.pop();
            if(t){
                st.push(t->left);
                st.push(t->right);
                swap(t->left,t->right);
            }
        }
        return root;
        */
    }

};

algorithm analysis

遍历一遍树，时间复杂度O(n)