156. 上下翻转二叉树 🔒
156. 上下翻转二叉树 🔒
🟠 🔖 树
深度优先搜索
二叉树
🔗 力扣
LeetCode
题目
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
题目大意
给你一个二叉树的根节点 root
,请你将此二叉树上下翻转,并返回新的根节点。 你可以按下面的步骤翻转一棵二叉树:
- 原来的左子节点变成新的根节点
- 原来的根节点变成新的右子节点
- 原来的右子节点变成新的左子节点
上面的步骤逐层进行。题目数据保证所有右节点要么是具有兄弟节点的叶节点(共享相同父节点的左节点),要么是空的。
解题思路
可以通过递归实现:
- 如果当前节点为空或者没有左子节点,直接返回当前节点。这是递归的终止条件。
- 对当前节点的左子节点进行递归调用,将其翻转后得到的新树作为新的根节点。
- 将当前节点的左子节点的左子节点指向当前节点的右子节点,将当前节点的左子节点的右子节点指向当前节点,将当前节点的左右子节点设为空。
- 返回经过翻转操作后的新树的根节点。
代码
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var upsideDownBinaryTree = function (root) {
if (!root || !root.left) return root;
// 递归调用,返回翻转后的新树的根节点
const newRoot = upsideDownBinaryTree(root.left);
// 调整节点指针
root.left.left = root.right;
root.left.right = root;
// 将当前节点的左右子节点设为空
root.left = null;
root.right = null;
// 返回新的根节点
return newRoot;
};