BiNode
难度:
标签:
题目描述
The data structure TreeNode is used for binary tree, but it can also used to represent a single linked list (where left is null, and right is the next node in the list). Implement a method to convert a binary search tree (implemented with TreeNode) into a single linked list. The values should be kept in order and the operation should be performed in place (that is, on the original data structure).
Return the head node of the linked list after converting.
Note: This problem is slightly different from the original one in the book.
Example:
Input: [4,2,5,1,3,null,6,0] Output: [0,null,1,null,2,null,3,null,4,null,5,null,6]
Note:
- The number of nodes will not exceed 100000.
代码结果
运行时间: 48 ms, 内存: 22.9 MB
/*
思路：
1. 使用Java Stream API的collect方法，将BST的节点收集到一个List中。
2. 遍历List，将节点的左指针设为null，右指针设为下一个节点。
3. 返回转换后的单向链表的头节点。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Solution {
public TreeNode flatten(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
inorderTraversal(root, nodes);
for (int i = 0; i < nodes.size() - 1; i++) {
nodes.get(i).left = null;
nodes.get(i).right = nodes.get(i + 1);
}
if (!nodes.isEmpty()) {
nodes.get(nodes.size() - 1).left = null;
nodes.get(nodes.size() - 1).right = null;
return nodes.get(0);
}
return null;
}
private void inorderTraversal(TreeNode node, List<TreeNode> nodes) {
if (node == null) return;
inorderTraversal(node.left, nodes);
nodes.add(node);
inorderTraversal(node.right, nodes);
}
}
解释
方法:
这个题解采用了深度优先搜索（DFS）的方法，特别是中序遍历，来实现二叉搜索树到单向链表的转换。中序遍历的顺序是左-根-右，这正好符合二叉搜索树的节点值从小到大的顺序。在遍历过程中，每访问一个节点，就将其左子节点设为空，并将其与前一个访问的节点（pre）的右子节点连接起来。如果是遍历到的第一个节点，则将其设置为链表的头节点。通过这种方式，可以在遍历结束时得到一个单向链表，链表中的节点顺序与二叉搜索树的中序遍历顺序相同。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在转换过程中，为什么要将当前节点的左子节点设为空，这样做的目的是什么？
▷🦆
递归函数`dfs`在遍历结束后如何确保所有节点都正确连接成单向链表？具体是通过哪些步骤实现的？
▷🦆
如何处理二叉搜索树中的空节点，它们在转换过程中有什么特殊的影响吗？
▷