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
C Solution 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* upsideDownBinaryTree(struct TreeNode* root) {
if (!root) return 0;
struct TreeNode dummy, *p = &dummy;
p->left = root->left;
p->right = root->right;
root->left = root->right = 0;
while (p->left) {
struct TreeNode *q = p->left;
p->left = q->left;
q->left = p->right;
p->right = q->right;
q->right = root;
root = q;
}
return root;
}
C Solution 2:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* upsideDownBinaryTree(struct TreeNode* root) {
struct TreeNode dummy, *p = &dummy;
p->left = root;
p->right = 0;
root = 0;
while (p->left) {
struct TreeNode *q = p->left;
p->left = q->left;
q->left = p->right;
p->right = q->right;
q->right = root;
root = q;
}
return root;
}
Summary:
- Solution 2 is much better
LeetCode: 156. Binary Tree Upside Down
近期评论