题目描述： 给定一个二叉树，其中所有的右节点要么是具有兄弟节点（拥有相同父节点的左节点）的叶节点，要么为空，将此二叉树上下翻转并将它变成一棵树， 原来的右节点将转换成左叶节点。返回新的根。
例子: 输入: [1,2,3,4,5] 输出: 返回二叉树的根 [4,5,2,#,#,3,1] 说明: 对 [4,5,2,#,#,3,1] 感到困惑? 下面详细介绍请查看 二叉树是如何被序列化的。 二叉树的序列化遵循层次遍历规则，当没有节点存在时，’#’ 表示路径终止符。 这里有一个例子: 上面的二叉树则被序列化为 [1,2,3,#,#,4,#,#,5].
方法1： 主要思路： （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) { TreeNode* parent=NULL; TreeNode* parent_right=NULL; while(root){ //刚好是一个首尾循环 TreeNode* root_left=root->left; root->left=parent_right; parent_right=root->right; root->right=parent; parent=root; root=root_left; } return parent;//返回 } };方法2： 主要思路： （1）递归； （2）将左子树进行递归，获得左子树的最终结果； （3）将左子树的最右边的叶子结点连接上根节点和右子树； （4）将根节点的左右子树置为空；
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* upsideDownBinaryTree(TreeNode* root) { //终止条件 if(root==nullptr||root->left==nullptr){ return root; } //左子树获得结果 TreeNode* new_root=upsideDownBinaryTree(root->left); TreeNode* tmp_root=new_root; //获得左子树的最右边的结点 while(tmp_root->right){ tmp_root=tmp_root->right; } //将最右边的结点连接上根节点和右子树 tmp_root->left=root->right; tmp_root->right=root; //置为空 root->left=nullptr; root->right=nullptr; return new_root; } };