【LeetCode】Binary Tree Upside Down

Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes
with a sibling (a left node that shares the same parent node) or empty,
flip it upside down and turn it into a tree where the original right nodes
turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},
　　1
　 / \
　 2 3
/ \
4 5
return the root of the binary tree [4,5,2,#,#,3,1].
　 4
　 / \
5 2
/ \
3 1

由于该树的特性，右子树只能是叶节点，因此使用一个栈就能记录从根节点到最左节点。

这些栈中的节点将逆序成为新的右子树的根节点。

原先的父节点成为右子节点，原先父节点的右子节点成为左子节点。

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) 
    {
        if(root == NULL)
            return root;

        stack<TreeNode*> s;    //left child list
        s.push(root);
        TreeNode* cur = root;
        while(cur->left)
        {
            s.push(cur->left);
            cur = cur->left;
        }
        TreeNode* newroot = s.top();
        cur = newroot;
        s.pop();
        while(!s.empty())
        {
            TreeNode* oldfather = s.top();
            s.pop();
            cur->left = oldfather->right;
            cur->right = oldfather;
            cur = oldfather;
            //reset
            cur->left = NULL;
            cur->right = NULL;
        }
        return newroot;
    }
};

我设计的测试用例如下，全部通过：

int main()
{
    Solution s;
    TreeNode* n1 = new TreeNode(1);
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n3 = new TreeNode(3);
    TreeNode* n4 = new TreeNode(4);
    TreeNode* n5 = new TreeNode(5);
    
    //1. {} expect {}
    TreeNode* ret = s.upsideDownBinaryTree(NULL);
    if(ret == NULL)
        cout << "1. pass" << endl;
    else
        cout << "1. fail" << endl;
    //2. {1} expect {1}
    n1 = new TreeNode(1);
    ret = s.upsideDownBinaryTree(n1);
    if(ret->val == 1 && n1->left == NULL && n2->left == NULL)
        cout << "2. pass" << endl;
    else
        cout << "2. fail" << endl;
    //3. {1,2} expect {2,#,1}
    n1 = new TreeNode(1);
    n2 = new TreeNode(2);
    n1->left = n2;
    ret = s.upsideDownBinaryTree(n1);
    if(ret->val == 2 && ret->left == NULL && ret->right->val == 1 && ret->right->left == NULL && ret->right->right == NULL)
        cout << "3. pass" << endl;
    else
        cout << "3. fail" << endl;
    //4. {1,2,3} expect {2,3,1}
    n1 = new TreeNode(1);
    n2 = new TreeNode(2);
    n3 = new TreeNode(3);
    n1->left = n2;
    n1->right = n3;
    ret = s.upsideDownBinaryTree(n1);
    if(ret->val == 2 && ret->left->val == 3 && ret->left->left == NULL && ret->left->right == NULL && ret->right->val == 1 && ret->right->left == NULL && ret->right->right == NULL)
        cout << "4. pass" << endl;
    else
        cout << "4. fail" << endl;
    //5. {1,2,#,3} expect {3,#,2,#,1}
    n1 = new TreeNode(1);
    n2 = new TreeNode(2);
    n3 = new TreeNode(3);
    n1->left = n2;
    n2->left = n3;
    ret = s.upsideDownBinaryTree(n1);
    if(ret->val == 3 && ret->left == NULL && ret->right->val == 2 && ret->right->left == NULL && ret->right->right->val == 1 && ret->right->right->left == NULL && ret->right->right->right == NULL)
        cout << "5. pass" << endl;
    else
        cout << "5. fail" << endl;
    //6. {1,2,3,4,5} expect {4,5,2,#,#,3,1}
    n1 = new TreeNode(1);
    n2 = new TreeNode(2);
    n3 = new TreeNode(3);
    n4 = new TreeNode(4);
    n5 = new TreeNode(5);
    n1->left = n2;
    n2->left = n4;
    n2->right = n5;
    n1->right = n3;
    ret = s.upsideDownBinaryTree(n1);
    if(ret->val == 4 && ret->left->val == 5 &&  ret->left->left == NULL && ret->left->right == NULL && ret->right->val == 2 && ret->right->left->val == 3 && ret->right->left->left == NULL && ret->right->left->right == NULL && ret->right->right->val == 1 && ret->right->right->left == NULL && ret->right->right->right == NULL)
        cout << "6. pass" << endl;
    else
        cout << "6. fail" << endl;
    //7. {1,2,#,3,4,5} expect {5,#,3,4,2,#,#,#,1}
    n1 = new TreeNode(1);
    n2 = new TreeNode(2);
    n3 = new TreeNode(3);
    n4 = new TreeNode(4);
    n5 = new TreeNode(5);
    n1->left = n2;
    n2->left = n3;
    n2->right = n4;
    n3->left = n5;
    ret = s.upsideDownBinaryTree(n1);
    if(ret->val == 5 && ret->left == NULL &&  ret->right->val == 3 && ret->right->left->val == 4 && ret->right->left->left == NULL && ret->right->left->right == NULL && ret->right->right->val == 2 && ret->right->right->left == NULL && ret->right->right->right->val == 1 && ret->right->right->right->left == NULL && ret->right->right->right->right == NULL)
        cout << "7. pass" << endl;
    else
        cout << "7. fail" << endl;
}

【LeetCode】Binary Tree Upside Down

推荐阅读