来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-upside-down
题目描述
给你一个二叉树的根节点 root ，请你将此二叉树上下翻转，并返回新的根节点。
你可以按下面的步骤翻转一棵二叉树：
原来的左子节点变成新的根节点
原来的根节点变成新的右子节点
原来的右子节点变成新的左子节点
上面的步骤逐层进行。题目数据保证每个右节点都有一个同级节点（即共享同一父节点的左节点）且不存在子节点。
示例 1：
输入：root = [1,2,3,4,5]
输出：[4,5,2,null,null,3,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 10] 内
1 <= Node.val <= 10
树中的每个右节点都有一个同级节点（即共享同一父节点的左节点）
树中的每个右节点都没有子节点
解题思路
经过观察发现仅仅是从下到上将父节点变成右结点，左结点变成父结点，右结点变成左结点，所以可以从下至上依次改变状态，可以使用栈来辅助寻找每一个结点，也可以使用前序遍历。
代码展示
栈辅助解法
/** * 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) { TreeNode* p = root; stack<TreeNode*> szStack; if(root) { while(p) { szStack.push(p); p = p->left; } root = szStack.top(); while(!szStack.empty()) { p = szStack.top(); szStack.pop(); if(szStack.empty()) { p->left = nullptr; p->right = nullptr; } else { TreeNode* q = szStack.top(); p->left = q->right; p->right = q; } } } return root; } };
前序遍历解法
/** * 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* mRoot; void dfs(TreeNode* root, TreeNode* fa) { if(!root) return; if(!root->left) mRoot = root; dfs(root->left, root); root->left = fa? fa->right : nullptr; root->right = fa; } TreeNode* upsideDownBinaryTree(TreeNode* root) { dfs(root,nullptr); return mRoot; } };
运行结果
