题解 | #二叉树展开为单链表#
二叉树展开为单链表
https://www.nowcoder.com/practice/421a1099535149c0828ad7a6e1ce7b40
public TreeNode expandTree (TreeNode root) { // write code here if (root == null) { return root; } TreeNode curr = root; while (curr != null) { if (curr.left != null) { // 找到左子树的最右节点 TreeNode prev = curr.left; while (prev.right != null) { prev = prev.right; } // 将当前节点的右子树接到左子树的最右节点 prev.right = curr.right; // 将当前节点的左子树移到右子树的位置 curr.right = curr.left; curr.left = null; } curr = curr.right; } return root; }
- 首先判断根节点是否为空,如果为空则直接返回。
- 使用一个指针curr从根节点开始遍历二叉树。
- 对于当前节点curr,如果它有左子树:找到左子树的最右节点prev。将当前节点的右子树接到左子树的最右节点的右指针上。将当前节点的左子树移到右子树的位置。将当前节点的左指针设为空。
- 移动curr指针到下一个节点,即当前节点的右子节点。
- 重复步骤3和步骤4,直到遍历完整个二叉树。
通过这种方式,我们可以在不使用额外空间的情况下,将二叉树展开为一条单链表。展开后的链表的顺序与二叉树的先序遍历顺序相同。
时间复杂度:O(n),其中n是二叉树的节点数。
空间复杂度:O(1),只使用了常数级别的额外空间。