156.Binary Tree Upside Down¶
Tags: Tree
Medium
Links: https://leetcode-cn.com/problems/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.
Example:
Input: [1,2,3,4,5]
1
/ \
2 3
/ \
4 5
Output: return the root of the binary tree [4,5,2,#,#,3,1]
4
/ \
5 2
/ \
3 1
Clarification:
Confused what [4,5,2,#,#,3,1]
means? Read more below on how binary tree is serialized on OJ.
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as [1,2,3,#,#,4,#,#,5]
.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (!root) return NULL;
if (!root -> left && !root -> right) return root;
TreeNode *newRoot = upsideDownBinaryTree(root -> left);
root -> left -> left = root -> right;
root -> left -> right = root;
root -> left = root -> right = NULL;
return newRoot;
}
};
给定一棵二叉树,所有右节点要么是空,要么是叶节点加左兄弟节点。 通俗来讲,这棵二叉树是一条左链,上面挂着若干右儿子,如下所示:
现在请将左链自下到上翻转成右链,并将所有右儿子换到左侧。