#P4063. 二叉树展开为链表
-
ID: 2304
Tried: 70
Accepted: 21
Difficulty: 5
二叉树展开为链表
题目内容
给你二叉树的根结点 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
二叉树展开为单链表
问题分析
将一棵二叉树原地展开为一个单链表，链表节点顺序等于二叉树的先序遍历（根→左→右）。展开后每个节点的左指针必须为 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;
}