二叉树展开为单链表

问题分析

将一棵二叉树原地展开为一个单链表，链表节点顺序等于二叉树的先序遍历（根→左→右）。展开后每个节点的左指针必须为 null，右指针指向下一个节点。

解题思路

方法一（递归后序反向处理）：

• 使用递归函数返回当前子树展开后的“尾节点”。
• 对于当前节点 root：先递归展开右子树，得到 rightTail；再递归展开左子树，得到 leftTail。
• 如果左子树存在，将左子树链表插入到 root.right，原来的右子树接在 leftTail.right；并将 root.left 置空。
• 返回优先为 rightTail，其次 leftTail，否则 root 本身。

方法二（迭代 + 栈）：

• 将根入栈，每次弹出一个节点 cur，将其右子节点（如果有）压栈，再将左子节点压栈。
• 如果栈不空，则 cur.right 指向栈顶节点；cur.left 置 null。

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(h)（递归栈或显式栈），h 为树高；最坏 O(n)。

代码实现

Python 代码

import sys
sys.setrecursionlimit(5000)

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

def build_tree(level_order):
    if not level_order or level_order[0] == 'null':
        return None
    
    root = TreeNode(int(level_order[0]))
    queue = [root]
    i = 1
    while i < len(level_order):
        current = queue.pop(0)
        # 构造左子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.left = TreeNode(int(level_order[i]))
            queue.append(current.left)
        i += 1
        # 构造右子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.right = TreeNode(int(level_order[i]))
            queue.append(current.right)
        i += 1
    return root

def flatten(root):
    def dfs(node):
        if not node:
            return None
        # 先展开左右子树
        left_tail = dfs(node.left)
        right_tail = dfs(node.right)
        # 如果左子树存在，将其插到右边
        if left_tail:
            left_tail.right = node.right
            node.right = node.left
            node.left = None
        # 返回尾节点：优先返回右子树尾，否则左子树尾，否则当前节点
        return right_tail or left_tail or node

    dfs(root)

def serialize(root):
    # 层序输出，不保留末尾 null
    from collections import deque
    if not root:
        return []
    q = deque([root])
    res = []
    while q:
        node = q.popleft()
        if node:
            res.append(str(node.val))
            q.append(node.left)
            q.append(node.right)
        else:
            res.append("null")
    while res and res[-1] == "null":
        res.pop()
    return res

if __name__ == "__main__":
    arr = sys.stdin.read().strip().split()
    root = build_tree(arr)
    flatten(root)
    print(" ".join(serialize(root)))

Java 代码

import java.io.*;
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    // 根据层次遍历构造二叉树
    public static TreeNode buildTree(String[] tokens) {
        if (tokens.length == 0 || tokens[0].equals("null"))
            return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (i < tokens.length) {
            TreeNode current = queue.poll();
            // 构造左子节点
            if (i < tokens.length && !tokens[i].equals("null")) {
                current.left = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(current.left);
            }
            i++;
            // 构造右子节点
            if (i < tokens.length && !tokens[i].equals("null")) {
                current.right = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(current.right);
            }
            i++;
        }
        return root;
    }

    public static TreeNode flatten(TreeNode root) {
        if(root == null) return null;
        TreeNode leftTail = flatten(root.left);
        TreeNode rightTail = flatten(root.right);
        if(leftTail != null) {
            leftTail.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        return rightTail != null ? rightTail : (leftTail != null ? leftTail : root);
    }

    public static List<String> serialize(TreeNode root) {
        List<String> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            TreeNode node = q.poll();
            if(node != null) {
                res.add(String.valueOf(node.val));
                q.offer(node.left);
                q.offer(node.right);
            } else {
                res.add("null");
            }
        }
        while(!res.isEmpty() && res.get(res.size()-1).equals("null")) {
            res.remove(res.size()-1);
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        TreeNode root = buildTree(arr);
        flatten(root);
        System.out.println(String.join(" ", serialize(root)));
    }
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& tokens) {
    if (tokens.empty() || tokens[0] == "null")
        return nullptr;
    
    TreeNode* root = new TreeNode(stoi(tokens[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (i < tokens.size()) {
        TreeNode* current = q.front();
        q.pop();
        // 构造左子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->left = new TreeNode(stoi(tokens[i]));
            q.push(current->left);
        }
        i++;
        // 构造右子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->right = new TreeNode(stoi(tokens[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

TreeNode* flatten(TreeNode* root) {
    if(!root) return nullptr;
    TreeNode* leftTail = flatten(root->left);
    TreeNode* rightTail = flatten(root->right);
    if(leftTail) {
        leftTail->right = root->right;
        root->right = root->left;
        root->left = nullptr;
    }
    return rightTail ? rightTail : (leftTail ? leftTail : root);
}

vector<string> serialize(TreeNode* root) {
    vector<string> res;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        if(node) {
            res.push_back(to_string(node->val));
            q.push(node->left);
            q.push(node->right);
        } else {
            res.push_back("null");
        }
    }
    while(!res.empty() && res.back() == "null")
        res.pop_back();
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> arr;
    string s;
    while(cin >> s) arr.push_back(s);
    TreeNode* root = buildTree(arr);
    flatten(root);
    auto ans = serialize(root);
    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << (i+1<ans.size() ? " " : "");
    }
    return 0;
}

题目内容

给你二叉树的根结点 $root$ ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 $TreeNode$ ，其中 $right$子指针指向链表中下一个结点，而左子指针始终为 $null$ 。
• 展开后的单链表应该与二叉树先序遍历顺序相同。

输入描述

一行二叉树的序列化数组$root$，节点值之间用空格隔开，空节点用null表示。

输出描述

层序遍历输出转化后的二叉树。末尾不保留多余的null。

样例1

输入

1 2 5 3 4 null 6

输出

1 null 2 null 3 null 4 null 5 null 6

样例2

输入

0

输出

0

提示

• 树中结点数在范围 $[0, 2000]$ 内
• $-100 <= Node.val <= 100$