当前位置：首页 > news >正文

从lc114. 二叉树展开为链表到lc-LCR 155二叉搜索树转化为排序的双向链表

news 2025/8/17 2:23:39

1 lc114. 二叉树展开为链表

1.1 描述

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
在这里插入图片描述

1.2 解法一：

先序遍历这棵树并且将节点加入到一个list中，随后按顺序将list中的每一个元素的left指针置换为空，right指针指向下一个节点

1.3 解法二：

按照先序遍历的倒叙方式遍历这棵二叉树，然后同时操作这个节点的左右指针。

class Solution {TreeNode pre;public void flatten(TreeNode root) {if(root==null){return;}flatten(root.right);flatten(root.left);root.right=pre;root.left=null;pre=root;}
}

1.3.1 为什么不能采用先序遍历，然后在过程中将左右指针进行相应的链接和置空呢？

答：因为先根遍历时进行正向的链接，会导致右子树断开，后续就无法遍历右子树中的节点

1.3.2 为什么先序的倒叙是代码中这样写的呢

答：先序遍历是"根-左-右"，那么先序的倒叙应该是"右-左-根"

1.3.3 为什么先序的倒叙可以避免右子树的撕裂？

答：其实右子树无论如何都会被断开一次，但是因为右子树中的节点都已经被正确处理完后才开始重新接上，后续就不需要遍历右子树了。

1.3.4 如果让展开后的单链表应该同样使用 TreeNode ，其中 left 子指针指向链表中下一个结点，而right 子指针始终为 null ，解法是不是基本相同？

答：对，遍历结构还是先序的倒叙遍历

class Solution {TreeNode pre;public void flatten(TreeNode root) {if(root==null){return;}flatten(root.right);flatten(root.left);root.left=pre;root.right=null;pre=root;}
}