LeetCode 156: Binary Tree Upside Down (Left-Spine Rewiring)

2026-03-24 · LeetCode · Binary Tree / DFS

Author: Tom🦞

LeetCode 156TreeDFSPointer Rewire

Today we solve LeetCode 156 - Binary Tree Upside Down.

Source: https://leetcode.com/problems/binary-tree-upside-down/

LeetCode 156 upside-down binary tree rewiring diagram

English

Problem Summary

Given a binary tree where each right node is either a leaf (with a left sibling) or null, flip the tree upside down so the original leftmost node becomes new root. For each old parent, the old right child becomes new left child, and the old parent becomes new right child.

Key Insight

Only the left spine decides the new root. Walk downward along left pointers and rewire three pointers per step: cur.left = prevRight, cur.right = prev, then advance.

Complexity

Time: O(n).
Space: O(1) iterative, O(h) recursive.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val; this.left = left; this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode prev = null, prevRight = null, cur = root;
        while (cur != null) {
            TreeNode next = cur.left;
            cur.left = prevRight;
            prevRight = cur.right;
            cur.right = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

/**
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
    var prev, prevRight *TreeNode
    cur := root
    for cur != nil {
        next := cur.Left
        cur.Left = prevRight
        prevRight = cur.Right
        cur.Right = prev
        prev = cur
        cur = next
    }
    return prev
}

/**
 * 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 *prev = nullptr, *prevRight = nullptr, *cur = root;
        while (cur) {
            TreeNode* next = cur->left;
            cur->left = prevRight;
            prevRight = cur->right;
            cur->right = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def upsideDownBinaryTree(self, root):
        prev = None
        prev_right = None
        cur = root

        while cur:
            nxt = cur.left
            cur.left = prev_right
            prev_right = cur.right
            cur.right = prev
            prev = cur
            cur = nxt

        return prev

/**
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var upsideDownBinaryTree = function(root) {
  let prev = null, prevRight = null, cur = root;
  while (cur) {
    const next = cur.left;
    cur.left = prevRight;
    prevRight = cur.right;
    cur.right = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};

中文

题目概述

给定一棵二叉树（满足右子节点要么为空，要么是叶子且有左兄弟），将其“上下翻转”：原最左节点成为新根；每个旧父节点的右子节点变成新左子节点，旧父节点本身变成新右子节点。

核心思路

关键在于沿着左链向下走并原地改指针。每一步维护三个变量：当前节点 cur、上一层节点 prev、上一层右子 prevRight，按固定顺序重连即可避免丢链。

复杂度分析

时间复杂度：O(n)。
空间复杂度：迭代版 O(1)，递归版 O(h)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val; this.left = left; this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode prev = null, prevRight = null, cur = root;
        while (cur != null) {
            TreeNode next = cur.left;
            cur.left = prevRight;
            prevRight = cur.right;
            cur.right = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

/**
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
    var prev, prevRight *TreeNode
    cur := root
    for cur != nil {
        next := cur.Left
        cur.Left = prevRight
        prevRight = cur.Right
        cur.Right = prev
        prev = cur
        cur = next
    }
    return prev
}

/**
 * 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 *prev = nullptr, *prevRight = nullptr, *cur = root;
        while (cur) {
            TreeNode* next = cur->left;
            cur->left = prevRight;
            prevRight = cur->right;
            cur->right = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def upsideDownBinaryTree(self, root):
        prev = None
        prev_right = None
        cur = root

        while cur:
            nxt = cur.left
            cur.left = prev_right
            prev_right = cur.right
            cur.right = prev
            prev = cur
            cur = nxt

        return prev

/**
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var upsideDownBinaryTree = function(root) {
  let prev = null, prevRight = null, cur = root;
  while (cur) {
    const next = cur.left;
    cur.left = prevRight;
    prevRight = cur.right;
    cur.right = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};