hot100 114.二叉树展开为链表

一、方法一：DFS+头插法构建链表。

1.思路：

（1）采用头插法构建链表，就是从节点6开始，在6的前面插入5，在5的前面插入4，以此类推。

（2）因此，要按照6->5->4->3->2->1的顺序访问节点，因此DFS顺序应该为右左根。

（3）将初始head节点置为空节点，在DFS的同时记录当前链表的头节点为head。

2.具体步骤：

（1）如果当前节点为空，直接返回。

（2）递归右子树。

（3）递归左子树。

（4）根节点的操作：把root.left置为空；头插法把root插在head的前面，也就是root.right = head；把head更新为root。

3.复杂度分析：

（1）时间复杂度：O(n)，其中n为二叉树的节点个数。

（2）空间复杂度：O(n)，递归需要O(n)的栈空间。

附代码：

class Solution { private TreeNode head; public void flatten(TreeNode root) { if(root == null){ return; } flatten(root.right); flatten(root.left); root.left = null; root.right = head; //头插法，相当于链表中的root.next = head // 头插法保证了head始终指向已处理的链表的头 // 这种方式保证了以O(1)的时间连接节点，无需再查找末尾 head = root; //更新head节点 } }

二、方法二：DFS+分治思想

1.分治思想：对于原二叉树，在计算出了根节点root = 1的左子树的链表2->3->4和右子树的链表5->6之后，接下来只需要把这三部分连起来。

（1）先把2->3->4和5->6连起来：也就是左子树链表尾节点4的right更新为节点5（即root.right），得到2->3->4->5->6。

（2）然后把1和2->3->4->5->6连起来，也就是节点1的right更新为节点2（即root.left），得到1->2->3->4->5->6。

（3）最后把root.left置为空。

2.在计算过程中需要知道左子树链表的尾节点4，因此DFS需要返回链表的尾节点。

3.链表合并完成后，返回合并后的链表的尾节点，也就是右子树链表的尾节点。如果右子树是空的，则返回左子树链表的尾节点。如果左右子树都是空的，就返回当前节点。

4.复杂度分析：

（1）时间复杂度：O(n)，其中n是二叉树的节点个数。

（2）空间复杂度：O(n)，递归需要O(n)的栈空间。

附代码：

class Solution { public void flatten(TreeNode root) { dfs(root); } private TreeNode dfs(TreeNode root){ if(root == null){ return null; } TreeNode leftTail = dfs(root.left); TreeNode rightTail = dfs(root.right); if(leftTail != null){ leftTail.right = root.right; //左子树链表 -> 右子树链表 root.right = root.left; //当前节点 -> 左右子树合并后的链表 root.left = null; } return rightTail != null ? rightTail : leftTail != null ? leftTail : root; } }

ACM模式：

import java.util.Scanner; import java.util.ArrayList; import java.util.List; import java.util.LinkedList; import java.util.Queue; // 定义二叉树节点类 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; this.left = null; this.right = null; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取输入的一行,并去除首尾空格 String input = scanner.nextLine().trim(); // 构建二叉树 TreeNode root = buildTree(input); // 将二叉树展开为链表 Solution solution = new Solution(); solution.flatten(root); // 输出展开后的链表（层序遍历格式，包含null） List<Integer> result = levelOrderTraversal(root); if (result == null || result.size() == 0) { System.out.println(); } else { for (int i = 0; i < result.size(); i++) { System.out.print(result.get(i)); if (i < result.size() - 1) { System.out.print(" "); } } System.out.println(); } scanner.close(); } // 根据输入字符串构建二叉树（层序遍历格式，null表示空节点） private static TreeNode buildTree(String input) { if (input == null || input.length() == 0) { return null; } String[] values = input.split(" "); if (values.length == 0 || values[0].equals("null")) { return null; } TreeNode root = new TreeNode(Integer.parseInt(values[0])); LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); int i = 1; while (!queue.isEmpty() && i < values.length) { TreeNode current = queue.remove(); // 处理左子节点 if (i < values.length && !values[i].equals("null")) { current.left = new TreeNode(Integer.parseInt(values[i])); queue.add(current.left); } i++; // 处理右子节点 if (i < values.length && !values[i].equals("null")) { current.right = new TreeNode(Integer.parseInt(values[i])); queue.add(current.right); } i++; } return root; } // 层序遍历，返回包含null的一维数组列表 private static List<Integer> levelOrderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.remove(); if (node == null) { result.add(null); continue; } result.add(node.val); queue.add(node.left); queue.add(node.right); } // 去除末尾的null（保持输出简洁） int lastIndex = result.size() - 1; while (lastIndex >= 0 && result.get(lastIndex) == null) { result.remove(lastIndex); lastIndex--; } return result; } } // 解题类，包含将二叉树展开为链表的方法 class Solution { private TreeNode head; public void flatten(TreeNode root) { if (root == null) { return; } flatten(root.right); flatten(root.left); root.left = null; root.right = head; // 头插法，相当于链表中的root.next = head // 头插法保证了head始终指向已处理的链表的头 // 这种方式保证了以O(1)的时间连接节点，无需再查找末尾 head = root; // 更新head节点 } }