先序遍历

输出[1,null,2,null,3,null,4,null,5,null,6]

解题思路

1、对于当前节点首先将其左子树展开为单链表并将左子树的最右节点连接到当前节点的右子树上。

2、然后将当前节点的右子树展开为单链表。

3、如果左子树不为空将当前节点的右子树设为展开后的左子树否则将左子树设为右子树。

Java实现

{return;}flattenHelper(root);}private

TreeNode

4//递归把1的右子树5-6移到1的左子树2-3-4的右子树下//

1//

6//把1的左子树2-3-4-5-6替换到右子树上把1的左子树置空//

1//

6//链表符合前序遍历了并且左子树全为null//下面是具体代码实现TreeNode

leftTail

flattenHelper(node.left);TreeNode

rightTail

而左子树的尾部接在当前节点的右侧。

这样展开后的链表顺序符合二叉树的先序遍历。

return

(rightTail

FlattenBinaryTreeToLinkedList();//

构造示例二叉树TreeNode

调用展开方法solution.flatten(root);//

current

时间复杂度O(n)其中n是二叉树中的节点数每个节点都需要访问一次。

空间复杂度O(h)递归调用栈的深度为树的高度。