156. Binary Tree Upside

🟠   🔖  树 深度优先搜索 二叉树  🔗 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 ，请你将此二叉树上下翻转，并返回新的根节点。 你可以按下面的步骤翻转一棵二叉树：

• 原来的左子节点变成新的根节点
• 原来的根节点变成新的右子节点
• 原来的右子节点变成新的左子节点

上面的步骤逐层进行。题目数据保证所有右节点要么是具有兄弟节点的叶节点（共享相同父节点的左节点），要么是空的。

解题思路

可以通过递归实现：

1. 如果当前节点为空或者没有左子节点，直接返回当前节点。这是递归的终止条件。
2. 对当前节点的左子节点进行递归调用，将其翻转后得到的新树作为新的根节点。
3. 将当前节点的左子节点的左子节点指向当前节点的右子节点，将当前节点的左子节点的右子节点指向当前节点，将当前节点的左右子节点设为空。
4. 返回经过翻转操作后的新树的根节点。

代码

/**
 * @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;
};