Description
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
The flattened tree should look like:
Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
Solution
DFS
平凡的写法。注意要将root的左右节点置为null,再向下面递归!否则下面的递归会改变root的结构。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode tail;
public void flatten(TreeNode root) {
dfs(root);
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
if (tail != null) {
tail.right = root;
}
tail = root;
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
root.right = null;
dfs(left);
dfs(right);
}
}
Iterative, time O(n), space O(1)
通过挂载左子树到右边来实现,很妙啊。
上面是题目及提示信息,大概意思是要按照前序遍历的顺序,将其变成一个单链表(但还是用树结构存),OK,开始分析下:
按照题目要求,它要把左子树的所有节点按照前序的顺序,挂载在右子树的链表中,那么我们首先遇到的第一个问题,把左子树挂载在右边,那之前的跟节点的右子树怎么处理?
上面这个问题,可以这样思考,我们假设已经把左子树挂载在右边,先忽视之前根节点的右子树,那么现在需要把其加载进去,那显然按照前序遍历的思想,我们肯定是把右子树挂载在左子树的某个位置,使得前序遍历时右子树在左子树之后被遍历到,那么只需要将右子树挂载到左子树的right most节点即可(其实挂载到其他地方也行,只要保证前序遍历顺序不变即可),OK,这是我们目前的想法。
再思考下,我们只是简单的将根节点的左子树挂载在它和它的右子树中间,并没有将其“捋平”,这样就涉及到递归的处理,反复的将其,加进去。那这样就涉及到刚开始的一个问题,我们是否真的需要把右子树搁在左子树前序遍历的最后一个元素中?如下图所示,这里显然,我们只需要将4 搁在2的右子树位置上,(第二张图),然后再递归的捋顺根节点的right即可。
/**
* 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) {
while (root != null) {
if (root.left != null) {
TreeNode rightMostInLeft = root.left;
while (rightMostInLeft.right != null) {
rightMostInLeft = rightMostInLeft.right;
}
// mount root.right to rightMostInLeft
// and mount root.left to root.right
rightMostInLeft.right = root.right;
root.right = root.left;
root.left = null;
}
root = root.right;
}
}
}