来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
题目描述
给定一棵二叉树，将它展开为链表，要求如下：
1.开后的单链表应该同样为二叉树（TreeNode），right 子指针指向链表中下一个结点，而左子指针始终为 null；
2.展开后的单链表二叉树的先序遍历顺序相同。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
题目分析
下面提供两种方法：
- 前序遍历
- 前序遍历 + 放入链表同时（方法一的延伸）
代码实现
public class ZhanKaiLianBiao114 {
public static void main(String[] args) {
ZhanKaiLianBiao114 zhanKaiLianBiao114 = new ZhanKaiLianBiao114();
/**
* 1
* 10 2
* 3 9
*/
TreeNode root = new TreeNode(1, new TreeNode(10), new TreeNode(2, new TreeNode(3), new TreeNode(9)));
zhanKaiLianBiao114.flatten2(root);
}
/**
* 【前序遍历 + 放入链表同时】
* <p>
* 时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历的同时对每个节点更新左右子节点的信息，更新子节点信息的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。
* <p>
* 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈的大小，栈内的元素个数不会超过 n。
*
* @param root
*/
public void flatten2(TreeNode root) {
if(root == null){
return;
}
// 栈，先进后出
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
TreeNode result = null;
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
if (result != null) {
result.left = null;
result.right = curr;
}
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
result = curr;
}
}
/**
* 【前序遍历】
* <p>
* 时间复杂度：O(n)，其中 n是二叉树的节点数。前序遍历的时间复杂度是 O(n)O(n)O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。
* <p>
* 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n。
*
* @param root
*/
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
// 前序遍历
preOrder(root, list);
System.out.println(list);
for (int i = 1; i < list.size(); i++) {
TreeNode result = list.get(i - 1);
TreeNode curr = list.get(i);
result.left = null;
result.right = curr;
}
System.out.println(root);
}
private void preOrder(TreeNode root, List<TreeNode> list) {
if (root != null) {
list.add(root);
preOrder(root.left, list);
preOrder(root.right, list);
}
}
}
两种方法复杂度一致
- 时间复杂度：O(n)
- 空间复杂度：O(n)
好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！
