# 问题 原题链接：[https://leetcode.com/problems/binary-tree-upside-down/](https://leetcode.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. ``` 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]. # 分析过程 - 输入：一棵二叉树，右节点要么为空要么一定会有对应的左节点。 - 输出：颠倒的二叉树，左节点变为根，右节点变为左节点。 - 思路：树倒置以后，实际上的逻辑是： - 左节点 -> 根节点 - 右节点 -> 左节点 - 根节点 -> 右节点 - 根据以上逻辑，进行指针赋值即可。有递归和循环两种解法。 # 解决方法 递归解法： ```cpp 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; } }; ``` 循环解法： ```cpp 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; } }; ```