leetcode[156] binary tree upside down

这题要收费了。只能网上看题目，我等屌丝也没法OJ测试了。网上看了后发现其实并非独创，其他的方也有类似的题。例如在这里，CareerCup上

先用了递归的想法，

    TreeNode *ans;
    TreeNode *helper156(TreeNode *root)
    {
        if (!root -> left && !root -> right)
        {
            ans = root; return root;
        }
        TreeNode *parent = helper156(root -> left);
        parent -> left = root -> right;
        parent -> right = root;
        root -> left = NULL;
        root -> right = NULL;
        return parent -> right;
    }
    TreeNode *UpsideDown(TreeNode *root)
    {
        if (root)
            helper156(root);
        return ans;
    }

在这里提到如果是非递归的那么和反转链表差不多Reverse Linked List II

    TreeNode *UpsideDown2(TreeNode *root)
    {
        if (!root -> left && !root -> right) return root;
        TreeNode *parent = NULL, *parentRight = NULL, *p = root;
        while(p)
        {
            TreeNode *left = p -> left;
            p -> left = parentRight;
            parentRight = p -> right;
            p -> right = parent;
            parent = p;
            p = left;
        }
        return parent;
    }

不用递归还是挺妙的啊。