LeetCode 156. 上下翻转二叉树（DFS）*

文章目录

1. 题目2. 解题

1. 题目

给定一个二叉树，其中所有的右节点要么是具有兄弟节点（拥有相同父节点的左节点）的叶节点，要么为空 将此二叉树上下翻转并将它变成一棵树， 原来的右节点将转换成左叶节点。返回新的根。

例子: 输入: [1,2,3,4,5] 1 / \ 2 3 / \ 4 5 输出: 返回二叉树的根 [4,5,2,#,#,3,1] 4 / \ 5 2 / \ 3 1 说明: 对 [4,5,2,#,#,3,1] 感到困惑? 下面详细介绍请查看 二叉树是如何被序列化的。 二叉树的序列化遵循层次遍历规则，当没有节点存在时，'#' 表示路径终止符。 这里有一个例子: 1 / \ 2 3 / 4 \ 5 上面的二叉树则被序列化为 [1,2,3,#,#,4,#,#,5].

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-upside-down 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：LeetCode 366. 寻找二叉树的叶子节点（上下翻转二叉树+BFS）

class Solution {//C++ public: TreeNode* upsideDownBinaryTree(TreeNode* root) { if(!root || !root->left) return root; TreeNode* l = root->left;//左右子节点存取来 TreeNode* r = root->right; root->left = NULL;//上下断开 root->right = NULL; TreeNode* p = upsideDownBinaryTree(l);//根节点 l->left = r;//跟上面连接起来 l->right = root; return p; } };

4 ms 9.8 MB

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # py3 def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode: if not root or not root.left: return root l = root.left r = root.right root.left = None root.right = None p = self.upsideDownBinaryTree(l) l.left = r l.right = root return p

32 ms 13.6 MB

---

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！