本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
本题来自 LeetCode：114. 二叉树展开为链表[1]
题目描述
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/
2 5
/
3 4 6
将其展开为：
1
2
3
4
5
6
递归版
题目分析
本题是二叉树的
前序遍历的变种，主要处理逻辑为：
示例分析
1
2 5
/
3 4 6
1
2 5
3 4 6
1
2 5
3 6
4
1
2
3
4
5
6
1
2
3
4
5
6
至此，整个过程就完成了。
题目解答
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
preOrder(root);
}
/**
* @param current 当前处理的节点
* @return 返回链表的尾节点
*/
public TreeNode preOrder(TreeNode current) {
// root = null的情况
if(current == null) {
return current;
}
TreeNode right = current.right;
TreeNode left = current.left;
if(left != null) {
//注意需要将左子树置null
current.left = null;
// 链表链接左子树
current.right = left;
// 获得链接的尾节点
current = preOrder(left);
}
if(right != null) {
// 链表链接右子树
current.right = right;
// 获得链接的尾节点
current = preOrder(right);
}
// 返回链接的尾节点
return current;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)
迭代版
题目分析
迭代的逻辑是将当前节点的右子树，链接到当前节点的左子树的最右节点的右子树上。如果不好理解这句话，直接看下面的示例过程。
示例分析
1
/
2
/
3 4
5
6
1
2
/
3 4
5
6
1
2
/
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
2
3
4
5
6
至此，整个过程就完成了。
题目解答
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
TreeNode node = null;
while(root != null) {
// 左子树为null，下一个迭代直接处理右子树
if(root.left == null) {
root = root.right;
continue;
}
// 左右子树都不为null
if(root.right != null) {
// 找到左子树的最右节点
node = root.left;
while(node.right != null) {
node = node.right;
}
// 将右子树链接到最右节点的右子树上
node.right = root.right;
}
// 将子子树链接到右子树上
root.right = root.left;
// 将左子树置null
root.left = null;
// 下一个迭代处理右子树
root = root.right;
}
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
其他递归版
这是我第一次写的解法，贴上来，记录下。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
flatten(root, null);
}
public TreeNode flatten(TreeNode current, TreeNode preNode) {
if(current == null) {
return preNode;
}
if(preNode == null) {
preNode = current;
} else {
preNode.right = current;
preNode = preNode.right;
}
TreeNode left = current.left;
TreeNode right = current.right;
current.left = null;
current.right = null;
if(left != null) {
preNode = flatten(left, preNode);
}
if(right != null) {
preNode = flatten(right, preNode);
}
return preNode;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(n)
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
