114. 二叉树展开为链表

题目描述

输入二叉树的根节点 root。把这棵树就地改造成一条“链表”，仍然使用原来的树节点。

改造后，每个节点的 right 指向链中的下一个节点，left 一律设为空。链中节点的先后次序必须与原树的先序遍历（根、左、右）一致。

函数不需要返回值，直接修改原树。结果树按层序数组表示，null 代表空位。

示例 1

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

解释：先序遍历为 1,2,3,4,5,6，展开后每个节点只有右孩子。

示例 2

输入：root = []
输出：null

解释：空树保持为空。

示例 3

输入：root = [0]
输出：[0]

解释：单个节点本身就是一条链。

数据范围

节点总数在 [0, 2000] 之间。
-100 <= Node.val <= 100

进阶：能否只用 O(1) 的额外空间，就地完成展开？

解题思路：寻找前驱节点

当前节点有左子树时，找左子树最右节点，将原右子树接到其右侧，再把整棵左子树移到右边。

为什么正确

cur 之前已经形成正确前序链且 left 为空；重连保持未处理部分的前序相对次序。

复杂度分析

时间 O(n)，额外空间 O(1)。

易错点

重连前先保存原右子树的连接；本题要求原地修改，不返回新链表。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def flatten(self, root):
        cur = root
        while cur:
            if cur.left:
                predecessor = cur.left
                while predecessor.right:
                    predecessor = predecessor.right
                predecessor.right = cur.right
                cur.right = cur.left
                cur.left = None
            cur = cur.right

class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode predecessor = cur.left;
                while (predecessor.right != null)
                    predecessor = predecessor.right;
                predecessor.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode* predecessor = cur->left;
                while (predecessor->right)
                    predecessor = predecessor->right;
                predecessor->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};

func flatten(root *TreeNode) {
	cur := root
	for cur != nil {
		if cur.Left != nil {
			predecessor := cur.Left
			for predecessor.Right != nil {
				predecessor = predecessor.Right
			}
			predecessor.Right = cur.Right
			cur.Right = cur.Left
			cur.Left = nil
		}
		cur = cur.Right
	}
}

var flatten = function(root) {
    let cur = root;
    while (cur) {
        if (cur.left) {
            let predecessor = cur.left;
            while (predecessor.right)
                predecessor = predecessor.right;
            predecessor.right = cur.right;
            cur.right = cur.left;
            cur.left = null;
        }
        cur = cur.right;
    }
};

function flatten(root: TreeNode | null): void {
    let cur = root;
    while (cur) {
        if (cur.left) {
            let predecessor = cur.left;
            while (predecessor.right)
                predecessor = predecessor.right;
            predecessor.right = cur.right;
            cur.right = cur.left;
            cur.left = null;
        }
        cur = cur.right;
    }
};

载入编辑器，自己跑一遍 →

其他解法

寻找前驱节点只用 O(1) 额外空间；逆前序递归和栈模拟都需要 O(h) 到 O(n) 的辅助空间，但更容易想到。

解法 2：逆前序递归时间 O(n)，空间 O(h)

按“右子树、左子树、根”的顺序递归，这正好是前序遍历的逆序。用 prev 记录上一个处理完的节点，它就是当前节点在链表中的后继。处理当前节点时令 right = prev、left = null，再把 prev 更新为当前节点。

代码很短，链表从尾部向头部构建，不会覆盖还没访问的子树。递归栈占 O(h) 空间，树退化时为 O(n)。

import sys
sys.setrecursionlimit(10000)

class Solution:
    def flatten(self, root):
        self.prev = None

        def visit(node):
            if not node:
                return
            visit(node.right)
            visit(node.left)
            node.right = self.prev
            node.left = None
            self.prev = node

        visit(root)

class Solution {
    private TreeNode prev;

    public void flatten(TreeNode root) {
        prev = null;
        visit(root);
    }

    private void visit(TreeNode node) {
        if (node == null) return;
        visit(node.right);
        visit(node.left);
        node.right = prev;
        node.left = null;
        prev = node;
    }
}

class Solution {
    TreeNode* prev = nullptr;
    void visit(TreeNode* node) {
        if (!node) return;
        visit(node->right);
        visit(node->left);
        node->right = prev;
        node->left = nullptr;
        prev = node;
    }
public:
    void flatten(TreeNode* root) {
        prev = nullptr;
        visit(root);
    }
};

func flatten(root *TreeNode) {
	var prev *TreeNode
	var visit func(node *TreeNode)
	visit = func(node *TreeNode) {
		if node == nil {
			return
		}
		visit(node.Right)
		visit(node.Left)
		node.Right = prev
		node.Left = nil
		prev = node
	}
	visit(root)
}

var flatten = function(root) {
    let prev = null;
    const visit = (node) => {
        if (!node) return;
        visit(node.right);
        visit(node.left);
        node.right = prev;
        node.left = null;
        prev = node;
    };
    visit(root);
};

function flatten(root: TreeNode | null): void {
    let prev: TreeNode | null = null;
    const visit = (node: TreeNode | null): void => {
        if (!node) return;
        visit(node.right);
        visit(node.left);
        node.right = prev;
        node.left = null;
        prev = node;
    };
    visit(root);
}

解法 3：栈模拟前序遍历时间 O(n)，空间 O(n)

用栈做前序遍历，弹出节点后先压右孩子、再压左孩子。弹出的节点接到 prev 的 right 上。孩子已经入栈，所以可以放心把当前节点的 left 置空、right 改写。

按前序顺序边遍历边连接，思路最直接，也没有递归深度问题。需要显式栈，空间不如主解法。

class Solution:
    def flatten(self, root):
        if not root:
            return
        stack = [root]
        prev = None
        while stack:
            node = stack.pop()
            if prev:
                prev.right = node
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
            node.left = None
            prev = node

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (prev != null) prev.right = node;
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
            node.left = null;
            prev = node;
        }
    }
}

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        vector<TreeNode*> stack{root};
        TreeNode* prev = nullptr;
        while (!stack.empty()) {
            TreeNode* node = stack.back();
            stack.pop_back();
            if (prev) prev->right = node;
            if (node->right) stack.push_back(node->right);
            if (node->left) stack.push_back(node->left);
            node->left = nullptr;
            prev = node;
        }
    }
};

func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	stack := []*TreeNode{root}
	var prev *TreeNode
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if prev != nil {
			prev.Right = node
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		node.Left = nil
		prev = node
	}
}

var flatten = function(root) {
    if (!root) return;
    const stack = [root];
    let prev = null;
    while (stack.length) {
        const node = stack.pop();
        if (prev) prev.right = node;
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
        node.left = null;
        prev = node;
    }
};

function flatten(root: TreeNode | null): void {
    if (!root) return;
    const stack: TreeNode[] = [root];
    let prev: TreeNode | null = null;
    while (stack.length) {
        const node = stack.pop()!;
        if (prev) prev.right = node;
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
        node.left = null;
        prev = node;
    }
}

二叉树专题的其他题目

查看二叉树全部题目 →