【二叉树】Leetcode 114. 二叉树展开为链表【中等】

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

解题思路

展开二叉树为单链表可以使用前序遍历的方式来实现。

• 1、对于当前节点，首先将其左子树展开为单链表，并将左子树的最右节点连接到当前节点的右子树上。
• 2、然后将当前节点的右子树展开为单链表。
• 3、如果左子树不为空，将当前节点的右子树设为展开后的左子树；否则，将左子树设为右子树。

Java实现

public class FlattenBinaryTreeToLinkedList {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public void flatten(TreeNode root) {if (root == null) {return;}flattenHelper(root);}private TreeNode flattenHelper(TreeNode node) {if (node == null) {return null;}//    1//   / \//  2   5// / \   \//3   4   6// 把2的右子树4放到2的左子树3的右子树上//      1//     / \//    2   5//   / \   \//  3   4   6//   \//    4//把2左子树3-4移到右子树下，把2的左子树置空//      1//     / \//    2   5//     \   \//      3   6//       \//        4//递归，把1的右子树5-6移到1的左子树2-3-4的右子树下//      1//     / \//    2   5//     \   \//      3   6//       \//        4//         \//          5//           \//            6//把1的左子树2-3-4-5-6替换到右子树上，把1的左子树置空//      1//       \//        2//         \//          3//           \//            4//             \//              5//               \//                6//链表符合前序遍历了，并且左子树全为null//下面是具体代码实现TreeNode leftTail = flattenHelper(node.left);TreeNode rightTail = flattenHelper(node.right);if (leftTail != null) {// 把右子树放到左子树的右子树上leftTail.right = node.right;// 把（带有右子树的）左子树赋给右子树node.right = node.left;// 右子树清空node.left = null;}//        在这里，rightTail 的优先级最高，然后是 leftTail，最后是 node。
//        这确保了在递归的过程中，当前子树展开后的链表的尾节点是按照
//        右子树、左子树、当前节点的顺序确定的。
//        这样的顺序保证了链表的正确连接，即右子树的尾部接在左子树的尾部，
//        而左子树的尾部接在当前节点的右侧。这样展开后的链表顺序符合二叉树的先序遍历。return (rightTail != null) ? rightTail : (leftTail != null) ? leftTail : node;}// 示例测试public static void main(String[] args) {FlattenBinaryTreeToLinkedList solution = new FlattenBinaryTreeToLinkedList();// 构造示例二叉树TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(5);root.left.left = new TreeNode(3);root.left.right = new TreeNode(4);root.right.right = new TreeNode(6);// 调用展开方法solution.flatten(root);// 打印展开后的链表TreeNode current = root;while (current != null) {System.out.print(current.val + " ");current = current.right;}}
}

时间空间复杂度

• 时间复杂度：O(n)，其中n是二叉树中的节点数，每个节点都需要访问一次。
• 空间复杂度：O(h)，递归调用栈的深度为树的高度。