一、题目

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

点击查看原题
难度级别： 中等

二、思路

1）数组记录

进行线序遍历，记录下遍历的节点，然后再统一修改指针

2）递归

定义flatten函数能够将其改为单链表，所以，进行先序遍历，先将左右子树进行递归，整理成单链表后，遍历左孩子单链表到尾节点，与右孩子单链表相连

三、代码

1）数组记录

  1. class Solution {
  2.     private List<TreeNode> ts;
  3.     public void flatten(TreeNode root) {
  4.         ts = new ArrayList();
  5.         inorder(root);
  7.         for (int i = 1; i < ts.size(); i++) {
  8.             ts.get(i-1).left = null;
  9.             ts.get(i-1).right = ts.get(i);
  10.         }
  11.     }
  12.     public void inorder(TreeNode root) {
  13.         if (root == null) {
  14.             return;
  15.         }
  16.         ts.add(root);
  17.         inorder(root.left);
  18.         inorder(root.right);
  19.     }
  20. }

时间复杂度O(n)，空间复杂度O(n)

2）递归

  1. class Solution {
  2.     public void flatten(TreeNode root) {
  3.         if (root == null) {
  4.             return ;
  5.         }
  6.         flatten(root.left);
  7.         flatten(root.right);
  8.         TreeNode memo = root.right;
  9.         root.right = root.left;
  10.         root.left = null;
  11.         TreeNode t = root;
  12.         while (t.right != null) {
  13.             t = t.right;
  14.         }
  15.         t.right = memo;
  16.     }
  17. }

时间复杂度O(n)，空间复杂度O(logn)