题目
将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说，用二叉树的 right 指针，来表示链表中的 next 指针。
注意事项
不要忘记将左儿子标记为 null，否则你可能会得到空间溢出或是时间溢出。
样例
1
\
1 2
/ \ \
2 5 => 3
/ \ \ \
3 4 6 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;
* }
* }
*/
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
* 前序遍历：根左右
* 修改根的right指向左部分
* 左部分的right指向右部分
*/
public void flatten(TreeNode root) {
// write your code here
// 空结点
if(root == null)
return;
// 左右结点都空
if(root.left==null && root.right==null)
return;
// 左结点空
if(root.left==null){
TreeNode right = root.right;
flatten(right);
return;
}
// 右节点空
if(root.right==null){
TreeNode left = root.left;
root.right = left; flatten(left);
root.left = null;// left结点设置为空
return;
}
// 左右结点都不空
TreeNode left = root.left;
TreeNode right = root.right;
root.right = left; flatten(left); TreeNode p = left;
while(p.right!=null){ // 找到left部分的最右结点
p = p.right;
}
p.right = right;
flatten(right); root.left = null; // left结点设置为空
return;
}
}