【MEDIUM】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
``````

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].

# 分析过程

• 输入：一棵二叉树，右节点要么为空要么一定会有对应的左节点。
• 输出：颠倒的二叉树，左节点变为根，右节点变为左节点。
• 思路：树倒置以后，实际上的逻辑是：
• 左节点 -> 根节点
• 右节点 -> 左节点
• 根节点 -> 右节点
• 根据以上逻辑，进行指针赋值即可。有递归和循环两种解法。

# 解决方法

``````class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
// 新的根节点是左子树递归到最深的左叶子
if (!root || !root->left) {
return root;
}
TreeNode *newRoot = upsideDownBinaryTree(root->left);
// 左节点->根节点
// 右节点->左节点
// 根节点->右节点
TreeNode *l = root->left;
TreeNode *r = root->right;
l->left = r;
l->right = root;
root->left = nullptr;
root->right = nullptr;

return newRoot;
}
};``````

``````class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
TreeNode *cur = root;
TreeNode *next = nullptr, *pre = nullptr;
TreeNode *tmp = nullptr;

while (cur) {
// 左节点->根节点
next = cur->left;
// 右节点->左节点
cur->left = tmp;
tmp = cur->right;
// 根节点->右节点
cur->right = pre;

pre = cur;
cur = next;
}

// 最后cur是空，pre是最终根节点
return pre;
}
};``````