0156. Binary Tree Upside Down

题目信息

题号:
  1. 上下翻转二叉树

难度:

Medium

主题:

二叉树、指针重连、递归返回、迭代状态压缩

原题:

LeetCode 0156

重点:

沿最左链确定新主干,把原右兄弟与原父节点分别接为新左右孩子,并在重连前保存未处理方向

题目重述

给定一棵满足特殊结构的二叉树:每个非空右孩子都是叶节点,并且一定有同父的左兄弟。把树上下翻转,使 原树最左侧叶节点成为新根;对原左链上的每组关系,原节点的右孩子变成其左孩子的新左孩子,原节点本身 变成其左孩子的新右孩子。返回翻转后的根节点。

允许原地修改节点指针。空树返回空,只有一个节点时返回该节点。

自建示例

    1                  4
   / \                / \
  2   3      ->       5   2
 / \                    / \
4   5                  3   1

层序输入 [1,2,3,4,5] 翻转后可表示为 [4,5,2,null,null,3,1]。原最左叶 4 成为根;对原节点 2,它的右孩子 5 成为 4 的左孩子,2 成为 4 的右孩子。

C++ 实现

class Solution {
private:
    TreeNode* flipAfterReachingLeftmost(TreeNode* root) {
        if (root == nullptr || root->left == nullptr) {
            return root;
        }

        TreeNode* newRoot = flipAfterReachingLeftmost(root->left);
        TreeNode* originalLeft = root->left;
        originalLeft->left = root->right;
        originalLeft->right = root;
        root->left = nullptr;
        root->right = nullptr;
        return newRoot;
    }

    TreeNode* flipAlongLeftSpine(TreeNode* root) {
        TreeNode* current = root;
        TreeNode* originalParent = nullptr;
        TreeNode* originalRightSibling = nullptr;

        while (current != nullptr) {
            TreeNode* nextLeft = current->left;
            TreeNode* nextRight = current->right;

            current->left = originalRightSibling;
            current->right = originalParent;

            originalParent = current;
            originalRightSibling = nextRight;
            current = nextLeft;
        }
        return originalParent;
    }

public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        return flipAlongLeftSpine(root);
    }
};

题解

先确定翻转真正作用在哪条路径

新根不是任意叶节点,而是从原根连续走 left 到达的最左节点。原左链 root -> left -> left -> ... 会反向成为新树的右主干。对左链上的每条父子边,原父节点还有一个受结构 约束的右孩子;翻转后这两个旧关系固定映射为:

originalLeft.left  = originalParent.right
originalLeft.right = originalParent

题目的右孩子限制很重要:右侧是与左孩子成对的叶节点,可以作为这一层整体搬到新左边;不存在任意右子树 还要递归翻转或选择落点的问题。原始搜索空间因此不是对所有边决定方向,而是沿唯一左链逐层执行固定重连。

为什么应先到达最左节点再回接

递归方案 flipAfterReachingLeftmost 先处理 root->left。终止条件是空树或没有左孩子;根据题目结构, 没有左孩子时也不会独自存在右孩子,所以该节点就是新根。

递归返回时,左侧更深部分已经翻转完,但当前 root 与原左孩子的引用仍可取得。此时把当前原右孩子接到 originalLeft->left,把当前原父节点接到 originalLeft->right。每一层都返回同一个最左叶 newRoot,最终公开调用取得新根。

旧父节点的两条边为何必须清空

重连后 originalLeft->right = root 已建立从新主干向旧父节点的边。若仍保留 root->left 指向 originalLeft,两个节点会互相指向形成环;原 root->right 又已经迁移成新左孩子,保留它会让同一 节点有两个父引用。代码因此把旧父节点的 left、right 都设为空,表示这一层原边已经消费完。

具体递归走读

对示例 1、2、4 组成的左链:

返回层

新连接

清除旧连接

到达 4

4 暂作新根

无需改动

返回原父 2

4.left=5、4.right=2

2.left=null、2.right=null

返回原父 1

2.left=3、2.right=1

1.left=null、1.right=null

注意第二次使用的是节点对象 2:上一层已把它的旧孩子清空,所以现在可以安全承载来自原父 1 的 新左右关系。

如何把递归帧压缩成三个滚动指针

递归返回时一层需要知道“当前节点的原父节点”和“原父节点的右孩子”。迭代法从根沿左链向下时直接携带:

  • current:这一轮将成为新主干节点;

  • originalParent:current 的原父节点,将成为它的新右孩子;

  • originalRightSibling:原父节点的右孩子,将成为它的新左孩子。

在覆盖 current->left、current->right 前,必须先保存 nextLeft、nextRight。nextLeft 是 尚未处理的下一主干节点;nextRight 会在下一轮成为它的 originalRightSibling。若直接改写后再读, 原树后续路径或右兄弟就会丢失。

current

进入时携带

改写后

1

父、右兄弟均为空

1.left=null、1.right=null;保存 2、3

2

originalParent=1、originalRightSibling=3

2.left=3、2.right=1;保存 4、5

4

originalParent=2、originalRightSibling=5

4.left=5、4.right=2;下一左节点为空

循环结束时,originalParent 正是最后处理的最左节点 4,也就是新根。

正确性、主解选择与复杂度

每轮对左链一层执行题目规定的唯一映射:原右兄弟成为新左孩子,原父成为新右孩子;保存的下一左指针保证 所有层都会处理,清除/覆盖旧边保证节点不会重复或成环。右孩子本来都是叶子,作为整体只迁移一次;所以 节点集合不变,最终结构与定义一致。

递归与迭代都只沿树高 h 的左链处理一次,时间 O(h),在该结构下也不超过 O(n)。递归使用 O(h) 调用栈,状态含义最接近自底向上回接;公开入口选择迭代版本,将这些帧压缩为三个滚动指针,工作 空间 O(1),但对赋值顺序的要求更严格。