描述
将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说，用二叉树的 right 指针来表示链表中的 next 指针。
注意事项
不要忘记将左儿子标记为 null，否则你可能会得到空间溢出或是时间溢出。
样例
1
\
1 2
/ \ \
2 5 => 3
/ \ \ \
3 4 6 4
\
5
\
6
挑战
不使用额外的空间耗费
思路
本题采用递归的方法解决，关键是要知道由左子树转化的链表的头和尾， 以及由右子树转化的链表的头和尾。头一定是二叉树的根节点，尾是右子树的尾（如果右子树不空）或者左子树的尾（如果右子树空，左子树不空）或者根（如果左右子树都是空）
代码
1 1
/ \ \
2 5 => 2
/ \ \ / \
3 4 6 3 4
\
5
\
6
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
- 遍历
用给的样例和样例 {1， 2， 3} 模拟下容易理解
public class Solution {
// 上一操作结点，全局变量
private TreeNode lastNode = null;
public void flatten(TreeNode root) {
// root为空时直接返回，不做任何操作
if (root == null) {
return;
}
// 这个 if 条件是进入左子树和右子树才开始执行
if (lastNode != null) {
lastNode.left = null;
// 这个 root 为当前递归层的根结点
lastNode.right = root;
}
// 移动 lastNode，此时问题转化为下一轮递归
lastNode = root;
TreeNode right = root.right;
// 多层递归把左边完全拆完才开始右边
flatten(root.left);
/* 下面这个地方不能写成 root.right ,比如一开始 lastnode 为根结点
* 然后对根结点左子树递归，在下一层递归调用中
* 如果满足 `if (lastNode != null)`将 lastnode 的左右孩子都重新赋值
* 那么递归结束回到当前层的时候，root.right 已经不是原来的右子树了
*/
flatten(right);
}
}
- 分治
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
helper(root);
}
// 扁平化的链表头结点一定是 root，helper 函数的作用是找到尾结点
private TreeNode helper(TreeNode root) {
if (root == null) {
return null;
}
// 左子树的尾结点
TreeNode leftlast = helper(root.left);
// 右子树的尾结点
TreeNode rightlast = helper(root.right);
// 左子树的头结点即 root.left 连接到 root.right
// root.right 连接到左子树的尾结点
if (leftlast != null) {
leftlast.right = root.right;
root.right = root.left;
root.left = null;
}
// 右子树尾结点存在时返回右子树尾结点
if (rightlast != null) {
return rightlast;
}
// 右子树尾结点不存在但左子树为结点存在时，返回左子树尾结点
if (rightlast == null && leftlast != null) {
return leftlast;
}
// 左右子树尾结点都不存在，返回 root 本身
return root;
}
}
- 非递归，用栈＋while循环(重点)
当前结点从栈中弹出后，且当前结点存在左右儿子，因为左儿子比右儿子后压栈， 所以
node.right = stack.peek();时会首先将左儿子连到当前结点后，
如果左儿子是叶子结点，则栈中不会添加新结点，当左儿子弹出后，栈顶就是右儿子，直接把右儿子连到了左儿子后面；
如果左儿子不是叶子结点也存在儿子，也好办，继续将左儿子的儿子压栈，问题转化成了以当前左儿子为根结点的拆链表问题；
上面说的是结点有左右儿子或者是叶子结点的情形，若只有一个子结点， 少了左儿子即少了插入左儿子的过程，少了右儿子即少了往左儿子后面连接的过程，并不影响算法
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
// 先压右结点，后压左结点
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
// connect
node.left = null;
// 此处是 if else
// node.right 在此处等同于 next
if (stack.empty()) {
node.right = null;
} else {
node.right = stack.peek();
}
}
}
}
