题目描述

Invert a binary tree.

Homebrew的作者去Google面试，挂在这个题上了。他回头就在twitter上把Google给喷了。。。

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.

样例

Input:

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

Output:

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

算法1

DFS即可

tree比较大时，会stack overflow。

C++ 代码

略

算法2

非递归解法

tree比较大时不会stack overflow

C++ 代码

    // iterative solution
    // 每次取栈顶node时，将其左右子树交换

    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;

        stack<TreeNode*> stk;
        TreeNode* p = root;
        while(p || stk.size()) {
            while(p){
                stk.push(p);
                p = p->left;
            }
            // p is null, take stack top
            p = stk.top(); stk.pop();
            // swap p's left and right
            auto temp = p->left;
            p->left = p->right;
            p->right = temp;
            // 访问右子树，此时是p->left
            p = p->left;
        }

        return root;
    }