二叉树转单链表

124 阅读 0 评论 82 点赞

我是靠谱客的博主俏皮斑马，这篇文章主要介绍二叉树转单链表，现在分享给大家，希望可以做个参考。

2019独角兽企业重金招聘Python工程师标准>>>

原题

　　Given a binary tree, flatten it to a linked list in-place.
　　For example,
　　Given

复制代码

　　The flattened tree should look like:

复制代码

题目大意

　　给定一棵二叉树，将它转成单链表，使用原地算法。

解题思路

　　从根结点（root）找左子树（l）的最右子结点（x），将root的右子树（r）接到x的右子树上（x的右子树为空），root的左子树整体调整为右子树，root的左子树赋空。

代码实现

树结点类

复制代码

1
2
3
4
5
6
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

算法实现类

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public void flatten(TreeNode root) {
TreeNode head = new TreeNode(-1);
head.right = root;
TreeNode node = head;
while (node.right != null) {
node = node.right;
if (node.left != null) {
TreeNode end = node.left;
while (end.right != null) {
end = end.right;
}
TreeNode tmp = node.right;
node.right = node.left;
node.left = null;
end.right = tmp;
}
}
head.right = null; // 去掉引用方便垃圾回收
}
}