将二叉树拆成链表

描述

将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说,用二叉树的 right 指针,来表示链表中的 next 指针。

注意事项

不要忘记将左儿子标记为 null,否则你可能会得到空间溢出或是时间溢出

样例


考察点
  • 二叉树
  • 递归算法
答案
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;
        return;
    }
    // 左右结点都不空
    TreeNode left = root.left;
    TreeNode right = root.right;
    root.right = left;
    flatten(left);
    TreeNode p = left;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
    flatten(right);

    root.left = null;
    return;
}