首页 > 代码库 > 【LeetCode】Binary Tree Upside Down
【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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。