# 156. Binary Tree Upside Down 上下翻转二叉树

@TOC

## # 题目描述

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
``````

## # 解题方法

### # 递归

``````/**
* 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) {
if (!root || !root->left) return root;
TreeNode* l = root->left;
TreeNode* r = root->right;
TreeNode* newRoot = upsideDownBinaryTree(root->left);
l->left = r;
l->right = root;
root->left = nullptr;
root->right = nullptr;
return newRoot;
}
};
``````

### # 迭代

pre保存新树的根节点; cur保存每个节点，每次向左下方移动; next保存cur->next; temp保存cur->right;

``````/**
* 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) {
TreeNode* cur = root, *pre = nullptr, *temp = nullptr, *nxt = nullptr;
while (cur) {
nxt = cur->left;
cur->left = temp;
temp = cur->right;
cur->right = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};
``````

## # 日期

2019 年 9 月 17 日 —— 听了hulu宣讲会，觉得hulu的压力不大