题目描述
给定一个二叉树，原地将它展开为链表。
示例：
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
思路
1.从根节点开始遍历，依次遍历右子树，若当前结点存在左子树，则进行如下操作。
- 遍历当前结点左子树的右子树，然后将左子树与右子树进行拼接
- 将当前结点的右子树指针指向左子树
- 将当前结点的左子树的指针置空
2.一直循环遍历到右子树结尾即可。
具体转变过程，可以参考下图：
左子树与右子树相连
将当前结点的右子树指针指向左子树
将当前结点的左子树的指针置空
Java代码实现
public void flatten(TreeNode root) {
while(root != null){
//如果当前结点的左子树不为null，说明需要接到右子树上
if(root.left != null){
TreeNode curLeft = root.left;
while(curLeft.right != null){
curLeft = curLeft.right;
}
//将左子树与右子树相连
curLeft.right = root.right;
//将当前结点的右子树指向改变
root.right = root.left;
//将当前结点的左子树置空
root.left = null;
}
//进行下一个结点的转换
root = root.right;
}
}
